মিন হিপ বাস্তবায়নের জন্য C++ প্রোগ্রাম

একটি বাইনারি হিপ হল একটি সম্পূর্ণ বাইনারি ট্রি যা হয় মিন হিপ বা ম্যাক্স হিপ। সর্বাধিক বাইনারি হিপে, বাইনারি হিপে উপস্থিত সমস্ত কীগুলির মধ্যে মূলের কীটি অবশ্যই সর্বাধিক হতে হবে। এই বৈশিষ্ট্যটি অবশ্যই বাইনারি ট্রির সমস্ত নোডের জন্য পুনরাবৃত্তিমূলকভাবে সত্য হতে হবে। মিন বাইনারি হিপ হল মিন হিপের মত।

অ্যালগরিদম

min_heap(): এর জন্য

Begin
   Declare function min_heap(int *a, int m, int n)
      Declare j, t of the integer datatype.
      Initialize t = a[m].
      j = 2 * m;
      while (j <= n) do
         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
   return
End.

build_minheap এর জন্য:

Begin
   Declare function build_minheap(int *a,int n).
      Declare k of the integer datatype.
      for(k = n/2; k >= 1; k--)
         Call function min_heap(a,k,n)
End.

উদাহরণ

#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<<"enter no of elements of array\n";
   cin>>n;
   int a[30];
   for (i = 1; i <= n; i++) {
      cout<<"enter 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();
}

আউটপুট

enter no of elements of array
5
enter element 1
7
enter element 2
6
enter element 3
2
enter element 4
1
enter element 5
4
Min Heap
1
4
2
6
7