C++で最大ヒープから最小値の要素を見つける方法

問題の概要

最大ヒープ（max heap）の中から、最も小さい値を持つ要素を探す方法を解説します。

以下のような最大ヒープを例に考えてみましょう。

最大ヒープでは、親ノードの値は必ずその子ノードの値以上になります。この性質により、最小値は必ず葉ノード（leaf node）のいずれかに存在すると結論できます。ヒープが n 個のノードを含む場合、葉ノードの数は ceil(n/2) 個になります。

また、最大ヒープは完全二分木であるため、配列として表現することができます。このとき、最初の葉ノードは floor(n/2) のインデックス以降に配置されます。上記の例では、最初の葉ノードはインデックス 5 に存在します。

アルゴリズム

最大ヒープから最小値を見つけるには、以下の手順を使用します。

1. ヒープ内の最初の葉ノードを見つけ、その値を最小値とする
2. 残りのすべての葉ノードを走査し、より小さい値を持つ葉が見つかれば最小値を更新する

C++での実装例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getMinElement(int *heap, int n){
   int minElement = heap[n / 2];
   for (int i = n / 2 + 1; i < n; ++i) {
      minElement = min(minElement, heap[i]);
   }
   return minElement;
}
int main(){
   int heap[] = {120, 90, 100, 70, 75, 80, 60, 25, 40, 35};
   cout << "Min value: " << getMinElement(heap, SIZE(heap)) << "\n";
   return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Min value: 25

計算量について

このアルゴリズムは、葉ノードのみを走査するため、ノード総数 n の約半分の要素を調べることになります。したがって時間計算量は O(n/2)、すなわち O(n) となります。追加のメモリは不要で、空間計算量は O(1) です。最大ヒープの構造上、ルートから辿るだけでは最小値を特定できないため、このように葉ノード全体を確認するのが効率的なアプローチです。