C++で最大ヒープ（Max Heap）を実装する方法とサンプルコード

二分ヒープ（Binary Heap）とは、完全二分木の構造を持ち、最小ヒープ（Min Heap）または最大ヒープ（Max Heap）のいずれかの性質を満たすデータ構造です。最大二分ヒープでは、ルートに位置するキーが、ヒープ内に存在するすべてのキーの中で最大値でなければなりません。この性質は、二分木内のすべてのノードに対して再帰的に成り立つ必要があります。最小二分ヒープも同様に、親ノードが子ノード以下になるという対称的な性質を持ちます。

アルゴリズム

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.

C++による実装例

以下は、配列から最大ヒープを構築する完全なC++プログラムです。ユーザーから要素数と各要素を入力として受け取り、build_maxheap関数によってヒープ化した結果を出力します。

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

実行結果

このプログラムを実行し、5つの要素「7, 6, 2, 1, 4」を入力した場合の出力例です。最大値である7が先頭に配置され、ヒープの性質が満たされていることが確認できます。

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

処理のポイント

• max_heap関数： 指定された位置mにある要素を適切な位置まで下ろす「sift-down（下向き調整）」操作を行います。子ノードと比較しながら、ヒープの性質が保たれるまで要素を入れ替えていきます。
• build_maxheap関数： 葉ノード以外の最後のノード（n/2番目）から順に根に向かってmax_heapを呼び出すことで、配列全体をO(n)の計算量で最大ヒープに変換します。