একটি বাইনারি হিপ হলো একটি কমপ্লিট বাইনারি ট্রি যা যেন Min Heap বা Max Heap। একটি Max Binary Heap-এ, রুটের কি সব কি থেকে ম্যাক্সিমাম হতে হবে। এই প্রপার্টি রিকার্সিভলি সকল নোডের জন্য সত্য হতে হবে। Min Binary Heap Min Heap-এর মতো।
অ্যালগরিদম
min_heap() ফাংশনের জন্য:
শুরু min_heap(int *a, int m, int n) ফাংশন ঘোষণা করুন 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_minheap-এর জন্য:
শুরু build_minheap(int *a,int n) ফাংশন ঘোষণা করুন। k ইন্টিজার ডেটা টাইপ ঘোষণা করুন। for(k = n/2; k >= 1; k--) min_heap(a,k,n) ফাংশন কল করুন শেষ।
উদাহরণ
#include <iostream> #include <conio.h> using namespace std; void min_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_minheap(int *a, int n) { int k; for(k = n/2; k >= 1; k--) { min_heap(a,k,n); } } int main() { int n, i; cout << "array-এ উপাদানের সংখ্যা লিখুন\n"; cin >> n; int a[30]; for (i = 1; i <= n; i++) { cout << "element " << (i) << endl; cin >> a[i]; } build_minheap(a, n); cout << "Min Heap\n"; for (i = 1; i <= n; i++) { cout << a[i] << endl; } getch(); }আউটপুট
array-এ উপাদানের সংখ্যা লিখুন 5 element 1 7 element 2 6 element 3 2 element 4 1 element 5 4 Min Heap 1 4 2 6 7
