实现最大堆的C ++程序

Binary Heap是完整的二叉树，可以是Min Heap或Max Heap。在最大二进制堆中，在二进制堆中存在的所有密钥中，根目录中的密钥必须最大。对于二叉树中的所有节点，此属性必须递归地为true。Min Binary Heap与MinHeap类似。

算法

对于max_heap：

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