ヒープとは？
ヒープ(Heap)は、常に最小値(または最大値)を素早く取り出せるように保たれた完全二分木です。優先度付きキュー(priority queue)の標準実装で、ダイクストラ最短経路・ハフマン符号・ジョブスケジューリングのように「次に最も急ぐもの」を繰り返し取り出す場面で使われます。
核心の一行: 「全部整列せず、極値1つだけをO(log n)で管理する」。 全体整列(O(n log n))が不要なとき、ヒープははるかに経済的です。
配列で表現する完全二分木
ヒープは通常1つの配列で実装します。インデックス i に対して
- •左の子 =
2i + 1、右の子 =2i + 2、親 =(i - 1) / 2
最小ヒープは常に「親 ≤ 両方の子」を満たし(最大ヒープは逆)、ルートに最小値があります。ただし兄弟同士の順序は保証されません — ヒープは「完全整列」ではなく「親子関係」だけを守ります。
2つの核心操作
挿入(push): 新しい値を配列末尾に入れ、親より小さい間は親と入れ替えて上へ上がります(sift-up)。定位置を見つけると止まります。
削除(pop): ルート(最小値)を取り出して返し、末尾要素をルートへ移し、小さい方の子と入れ替えて下へ降ります(sift-down)。
どちらも木の高さ分しか動かないので各O(log n)です。
動作原理
ステップ1. push: 末尾に追加 → 親と比較 → 規則違反なら交換(sift-up) → ルートまで、または止まるまで繰り返し。
ステップ2. peek: ルート(arr[0])を見ればO(1)で最小値がわかります。
ステップ3. pop: ルートと末尾を交換し末尾を削除 → 新ルートを小さい子と比較 → 違反なら交換(sift-down) → 葉まで、または止まるまで繰り返し。
AlgoNoteの可視化は、sift-upとsift-downでどのノード同士が比較・交換されるかを色でステップごとに示します。
時間計算量と空間計算量
| 操作 | 計算量 |
|---|---|
| 挿入/削除 | O(log n) |
| 最小値確認(peek) | O(1) |
| ヒープ構築(build) | O(n) |
| 空間 | O(n) |
例で追ってみる
最小ヒープに 5, 3, 8, 1 を順に入れます。
- •5挿入 → [5]
- •3挿入 → 親5より小さく上がる → [3, 5]
- •8挿入 → 親3より大きくそのまま → [3, 5, 8]
- •1挿入 → 5より小さく、さらに3より小さく上がる → [1, 3, 8, 5]
ここでpopすると最小値1が先に出ます。
よくあるミス
- •完全整列との勘違い: ヒープ配列をそのまま出力しても整列されていません(兄弟順序は未保証)。
- •最小/最大の混同: 比較の不等号の向き1つで最小ヒープ↔最大ヒープが変わります。
- •任意要素の削除: 位置がわからないと探索にO(n)。位置がわかればその場でsiftしてO(log n)。
AlgoNoteで直接確認しましょう
値が挿入時に上がり(sift-up)、ルートが抜けるとき下がる(sift-down)過程をAlgoNoteでステップごとに確認できます。