バイナリヒープ完全ガイド：実装・操作・O(n)ビルドの仕組みと応用
エバープレイ編集部バイナリヒープとは
バイナリヒープ（binary heap）は、優先度付きデータを効率よく扱うための完全二分木（complete binary tree）に基づくデータ構造です。典型的には配列で表現され、ヒープ性（heap property）を満たします。最小値を根に持つものを「最小ヒープ（min-heap）」、最大値を根に持つものを「最大ヒープ（max-heap）」と呼びます。バイナリヒープは優先度付きキュー（priority queue）の実装に広く使われ、挿入（insert）や最小値（最大値）の取り出し（extract-min / extract-max）、キーの減少（decrease-key）などを効率的に行えます。
基本特性と表現
- 構造特性：完全二分木。すべてのレベルが満たされているか、最後のレベルのみ左詰めで埋まる。
- ヒープ性：任意の親ノードはその子ノードより優先度（値）が高い（min-heapなら親 ≤ 子、max-heapなら親 ≥ 子）。
- 配列表現：ノードを配列に左から右へレベル順（レベルオーダー）に格納する。インデックスの計算によって親・子へ O(1) でアクセスできる。
- 時間計算量：代表的操作は O(log n)（insert, extract-min/max, decrease-key）、ビルド（build-heap）は O(n）で実行可能。
- 空間計算量：O(n)。追加のポインタは不要で配列の連続領域に格納するためメモリ局所性が良い。
インデックスの計算（1-based と 0-based）
配列インデックスには 1-based（配列の最初を 1 とする）と 0-based（0 を開始）があります。式は以下の通り：
- 1-based: parent(i) = floor(i / 2), left(i) = 2i, right(i) = 2i + 1
- 0-based: parent(i) = floor((i - 1) / 2), left(i) = 2i + 1, right(i) = 2i + 2
どちらも正しく機能しますが、実装言語や慣習に応じて使い分けます。0-based は多くのプログラミング言語で自然です。
主要操作とアルゴリズム
以下では最小ヒープ（min-heap）を例に操作を説明します。
挿入（insert / push）
新しい要素を配列の末尾に追加し、親と比較して順序が崩れていれば上方向に交換（sift-up / bubble-up）してヒープ性を回復します。高さは O(log n) なので時間計算量は O(log n) です。
最小取り出し（extract-min / pop）
根（最小値）を取り出し、配列末尾の要素を根に置いてから子と比較して下方向に落としていく（sift-down / heapify-down）ことでヒープ性を回復します。こちらも O(log n) です。
キーの減少（decrease-key）
あるノードのキーを小さくする（min-heap の場合）とヒープ性が破られる方向は親側なので、sift-up を用いて調整します。時間計算量は O(log n)。任意ノードの削除は、キーを -∞（または十分小さい値）にしてから extract-min する方法で実現できます。
配列インデックスを使った擬似コード（簡略）
// 0-based 想定
void siftUp(array A, int i) {
while (i > 0 && A[parent(i)] > A[i]) {
swap(A[parent(i)], A[i]);
i = parent(i);
}
}
void siftDown(array A, int i, int n) {
while (true) {
int l = 2*i + 1;
int r = 2*i + 2;
int smallest = i;
if (l < n && A[l] < A[smallest]) smallest = l;
if (r < n && A[r] < A[smallest]) smallest = r;
if (smallest == i) break;
swap(A[i], A[smallest]);
i = smallest;
}
}
ビルドヒープ（build-heap）とその計算量 O(n) の理由
n 個の要素からヒープを作る単純な方法は、配列に要素を入れた後、下から順に各ノードに対して sift-down を行うものです。具体的には、最後の内部ノード floor(n/2)-1 から 0 まで順に heapify（sift-down）します。計算量は直感的に O(n log n) に見えるかもしれませんが、実際には O(n) です。
理由は各深さに存在するノード数とその操作コストを合計すると、浅いレベルのノード数が多いが移動量は小さい一方で、深いレベルは逆というバランスが取れており、全体の合計が線形になるためです。形式的には、コストは Σ_{h=0..H} (number of nodes at height h) × O(h) で示され、これを評価すると O(n) に収束します（詳細はアルゴリズム教科書参照）。
ヒープソートとの関係
バイナリヒープを使えばヒープソート（heap sort）を行えます。手順は：
- 配列をヒープに変換（build-heap） — O(n）
- 最大（または最小）を抜き出して配列末尾に置き、ヒープサイズを1つ減らす操作を n 回繰り返す — 各 O(log n)
合計で O(n log n) の比較ソートとなり、インプレース（追加配列不要）である一方、安定（stable）ではありません。また、平均・最悪ともに O(n log n) を満たします。
応用例
- 優先度付きキューの実装（OS のスケジューラ、イベント駆動シミュレーション等）
- Dijkstra の最短経路アルゴリズム（辺の重みが非負の場合） — decrease-key を使って効率化
- Prim の最小全域木（MST）アルゴリズム
- ヒープソートによる整列
- リアルタイムランキングや上位 k 要素の保持（最大ヒープ／最小ヒープを用途に応じて使い分け）
バイナリヒープと他のヒープ構造の比較
- Fibonacci ヒープ：理論的には decrease-key が O(1)（アモルタイズ）で、Dijkstra などのアルゴリズムで総計 O(m + n log n) を達成できる。ただし実装が複雑で定数係数が大きい。
- 二項ヒープ（binomial heap）：合併（merge）が O(log n) だが操作特性が異なる。
- d-ary ヒープ（d-ary heap）：子の数を d に増やすことで deepen（上昇）のコストを減らし、extract のコストを調整できる。Dijkstra で decrease-key が頻繁な場合は d を大きくすることで性能向上が見込める。
- 二分探索木（BST）や平衡二分木（AVL, Red-Black）：キーの順序を保ちながら検索・範囲クエリが得意だが、優先度の抜き出し（最小／最大）だけならバイナリヒープの方が単純で速い。
実装上の注意点とパフォーマンス
- メモリ局所性：配列に連続して格納するためキャッシュヒット率が良く、実用上の性能は高い。
- 安定性：同値の要素間の順序は保持されない（安定ではない）。安定にしたい場合はキーに副次的なタイムスタンプなどを付与する。
- メモリ管理：サイズの動的変化には配列リサイズが必要（例えば倍増戦略）。頻繁なリサイズはコストがかかるので適切に容量を確保する。
- 0-based／1-based の混同に注意：親子インデックス計算の間違いはバグの原因になりやすい。
- スレッド安全性：並列化は単純ではない。ロックや並列アルゴリズムを用いる必要がある。
よくある誤解
- 「ヒープはソート済み配列と同等」：ヒープは順序の一部（親子関係）しか保証しないので、全体がソートされるわけではありません。最小値だけは即座に取得可能ですが、次点以降は逐次取り出しが必要です。
- 「ビルドは常に O(n log n)」：前述の通り、適切な下からの heapify によるビルドは O(n) です。
- 「Fibonacci ヒープは常に速い」：理論上のアドバンテージはありますが、実装の複雑さと定数因子により小・中規模問題ではバイナリヒープの方が実用的な場合が多いです。
実務的な選択基準
実装の単純さ、メモリ局所性、定数係数の小ささから、一般的にはバイナリヒープが優先度付きキューの第一選択となります。特に decrease-key が稀であったり、大規模でも連続メモリの利点が活きる場合に適しています。逆に、decrease-key が非常に頻繁に行われるグラフアルゴリズムなどでは、理論的に有利な代替ヒープを検討する価値があります。
まとめ
バイナリヒープは配列で表現される完全二分木に基づくシンプルかつ高速な優先度付きデータ構造です。主要操作は O(log n) で、ビルドは O(n) です。実装が容易でメモリ局所性もよいため、多くの実用的な用途で第一選択となります。用途や操作の偏りに応じて d-ary ヒープや Fibonacci ヒープなどの代替構造も検討しますが、実際のアプリケーションではバイナリヒープのシンプルさと実効性能が重視されます。
参考文献
- Binary heap — Wikipedia
- Binary Heap Operations (Tutorials & Examples)
- Heap and Heap Sort — Lecture notes (Cambridge)
- Fibonacci heap — Wikipedia (比較参照)
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms（教科書）
投稿者プロフィール
