C++で最小ヒープ（Min Heap）を実装するプログラム：アルゴリズムとサンプルコードを解説

二分ヒープ（Binary Heap）は完全二分木の一種で、「最小ヒープ（Min Heap）」または「最大ヒープ（Max Heap）」のいずれかとして構成されます。最大二分ヒープでは、根（ルート）のキーがヒープ内のすべてのキーの中で最大でなければならず、この性質は木のすべてのノードに対して再帰的に成立している必要があります。最小二分ヒープはその逆で、親ノードのキーが常に子ノードのキー以下であることが保証されるデータ構造です。

本記事では、C++を使って最小ヒープを構築するプログラムを、アルゴリズム・サンプルコード・実行結果とあわせてわかりやすく解説します。

アルゴリズム

min_heap() の擬似コード

開始
    関数 min_heap(int *a, int m, int n) を宣言
        整数型の変数 j, t を宣言
        t = a[m] で初期化
        j = 2 * m
        j <= n の間繰り返し
            もし (j < n かつ a[j+1] < a[j]) ならば
                j = j + 1
            もし (t < a[j]) ならば
                ループを抜ける
            そうでなく (t >= a[j]) ならば
                a[j / 2] = a[j]
                j = 2 * j
        a[j / 2] = t
    return
終了

min_heap() は、位置 m の要素を起点に、子ノードと値を比較しながら適切な位置へ沈める（下降させる）ことで、その部分木がヒープ条件を満たすように修正する関数です。

build_minheap() の擬似コード

開始
    関数 build_minheap(int *a, int n) を宣言
        整数型の変数 k を宣言
        for (k = n / 2; k >= 1; k--)
            関数 min_heap(a, k, n) を呼び出す
終了

build_minheap() は、最後の内部ノード（添字 n/2）から根に向かって順に min_heap() を呼び出すことで、配列全体を最小ヒープへと変換します。

C++による実装例

#include <iostream>
#include <conio.h>
using namespace std;

// 位置mを起点にヒープ条件を回復させる関数
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<<"配列の要素数を入力してください\n";
    cin>>n;
    int a[30];
    for (i = 1; i <= n; i++) {
        cout<<"要素 "<<(i)<<" を入力"<<endl;
        cin>>a[i];
    }
    build_minheap(a, n);
    cout<<"最小ヒープ\n";
    for (i = 1; i <= n; i++) {
        cout<<a[i]<<endl;
    }
    getch();
}

※ conio.h および getch() はWindows環境固有の機能です。LinuxやmacOSで動作させる場合は、これらを削除するか cin.get() に置き換えてください。

実行結果

配列の要素数を入力してください
5
要素 1 を入力
7
要素 2 を入力
6
要素 3 を入力
2
要素 4 を入力
1
要素 5 を入力
4
最小ヒープ
1
4
2
6
7

実行結果のポイント

入力配列 {7, 6, 2, 1, 4} は、ヒープ構築後に {1, 4, 2, 6, 7} となります。ここで注意したいのは、出力が昇順にソートされてはいないという点です。ヒープは配列上で「a[i] ≤ a[2i] かつ a[i] ≤ a[2i+1]」という親子間の大小関係だけを保証するデータ構造だからです。実際、先頭の 1 の子（4 と 2）、さらに 4 の子（6 と 7）はいずれも親以上の値となっており、最小ヒープの条件を正しく満たしています。

まとめ

本プログラムでは、個々の部分木を修正する min_heap() と、配列全体をヒープ化する build_minheap() を組み合わせることで、任意の整数配列を最小ヒープへ変換しました。ヒープの構築は O(n) で行えるため非常に効率的であり、優先度付きキューやヒープソートなど、さまざまなアルゴリズムの基礎となる重要なデータ構造です。