Chương trình C ++ để triển khai Min Heap

Một đống nhị phân là một cây nhị phân hoàn chỉnh có thể là Min Heap hoặc Max Heap. Trong một đống nhị phân tối đa, khóa ở gốc phải lớn nhất trong số tất cả các khóa có trong đống nhị phân. Thuộc tính này phải đúng đệ quy cho tất cả các nút trong Cây nhị phân. Min Binary Heap tương tự như Min Heap.

Thuật toán

Đối với 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.

Đối với 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.

Ví dụ

#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();
}

Đầu ra

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