C++で最小ヒープから最大要素を効率的に求める方法

問題の概要

最小ヒープ(min-heap)が与えられたとき、その中に含まれる最大要素を見つけるプログラムを作成します。

例

入力として次のような最小ヒープが与えられたとします。

この場合、最大要素は 55 となります。

アルゴリズムの考え方

最小ヒープには重要な性質があります。

• 親ノードは必ず子ノード以下の値を持つ

この性質から、次のように結論づけられます。

• 葉以外のノード(内部ノード)は、少なくとも1つの子ノードより小さい値を持つため、最大要素になることはない
• したがって、最大要素は必ず葉ノードの中に存在する

つまり、配列で表現されたヒープにおいて、インデックス n/2 以降(葉ノードに相当する部分)だけを走査すればよいことになります。

計算量

走査対象は要素数の約半分であるため、時間計算量は O(n)、追加のメモリ使用量は O(1) となります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int getMaxElement(int *heap, int n) {
    // 葉ノードの先頭(n/2番目)を初期値とする
    int maxVal = heap[n / 2];
    for (int i = n / 2 + 1; i < n; ++i) {
        maxVal = max(maxVal, heap[i]);
    }
    return maxVal;
}

int main() {
    int heap[] = {15, 27, 22, 35, 29, 55, 48};
    int n = sizeof(heap) / sizeof(heap[0]);
    cout << "Maximum element = " << getMaxElement(heap, n) << endl;
    return 0;
}

実行結果

Maximum element = 55

まとめ

最小ヒープの性質「親 ≤ 子」を利用することで、探索範囲を葉ノードのみに限定でき、無駄な比較を省けます。全要素を走査する場合と比べて処理量を約半分に抑えられるのがポイントです。