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

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

অ্যালগরিদম

সর্বোচ্চ_হিপের জন্য:

Begin
   Declare function max_heap ()
      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_maxheap এর জন্য:

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

উদাহরণ

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

আউটপুট

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