একটি বাইনারি হিপ হলো একটি কমপ্লিট বাইনারি ট্রি যা যেন Min Heap বা Max Heap। একটি Max Binary Heap-এ, রুটের কি সব কি থেকে ম্যাক্সিমাম হতে হবে। এই প্রপার্টি রিকার্সিভলি সকল নোডের জন্য সত্য হতে হবে। Min Binary Heap Min Heap-এর মতো।
অ্যালগরিদম
max_heap-এর জন্য:
শুরু max_heap() ফাংশন ঘোষণা করুন j, t ইন্টিজার ডেটা টাইপ ঘোষণা করুন। t = a[m] আরম্ভ করুন। j = 2 * m। while (j <= n) করুন if (j < n && a[j+1] > a[j]) then j = j + 1 if (t > a[j]) then break else if (t <= a[j]) then a[j / 2] = a[j] j = 2 * j a[j/2] = t রিটার্ন শেষ।
build_maxheap-এর জন্য:
শুরু build_maxheap(int *a,int n) ফাংশন ঘোষণা করুন। k ইন্টিজার ডেটা টাইপ ঘোষণা করুন। for(k = n/2; k >= 1; k--) max_heap(a,k,n) ফাংশন কল করুন শেষ।
উদাহরণ
#include <iostream> using namespace std; void max_heap(int *a, int m, int n) { int j, t; t = a[m]; j = 2 * m; while (j <= n) { if (j < n && a[j+1] > a[j]) j = j + 1; if (t > a[j]) break; else if (t <= a[j]) { a[j / 2] = a[j]; j = 2 * j; } } a[j/2] = t; return; } void build_maxheap(int *a,int n) { int k; for(k = n/2; k >= 1; k--) { max_heap(a,k,n); } } int main() { int n, i; cout << "array-এ উপাদানের সংখ্যা লিখুন\n"; cin >> n; int a[30]; for (i = 1; i <= n; i++) { cout << "elements " << (i) << endl; cin >> a[i]; } build_maxheap(a,n); cout << "Max Heap\n"; for (i = 1; i <= n; i++) { cout << a[i] << endl; } }আউটপুট
array-এ উপাদানের সংখ্যা লিখুন 5 elements 1 7 elements 2 6 elements 3 2 elements 4 1 elements 5 4 Max Heap 7 6 2 1 4
