최소 힙을 구현하는 C++ 프로그램

이진 힙은 최소 힙 또는 최대 힙인 완전한 이진 트리입니다. Max Binary Heap에서 루트의 키는 Binary Heap에 있는 모든 키 중 최대값이어야 합니다. 이 속성은 이진 트리의 모든 노드에 대해 재귀적으로 true여야 합니다. 최소 바이너리 힙은 최소 힙과 유사합니다.

알고리즘

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