女性向けエンジニアスクール
3秒でわかる
最大値または最小値を根に保つ木構造。全体を並べ替えずに先頭の 1 個だけ即座に取れるので、優先度つきの処理に使われます。
もう少し詳しく
どういうものか
ヒープは、親が子より常に大きい、または常に小さいという条件を保った二分木です。前者を最大ヒープ、後者を最小ヒープと呼びます。根には全体の最大値または最小値が来ます。
条件は親子の関係だけで、兄弟どうしの大小は決まっていません。完全に並んでいるわけではないぶん、要素の出し入れが速く済みます。
木といっても実装は配列 1 本です。添字 i の子が 2i+1 と 2i+2 になる規則で並べるため、ポインタを持つ必要がありません。
なぜ必要か
「今いちばん優先度が高いものを取り出す」という処理を繰り返す場面で効きます。取り出しも追加も要素数の対数に比例する時間で終わり、10 万件でも 17 回程度の比較で済みます。
毎回ソートし直すと要素数かける対数の時間がかかり、線形探索で最大値を探すと要素数に比例します。どちらもヒープより遅くなります。タスクスケジューラ、ダイクストラ法の経路探索、上位 k 件の抽出などが典型的な用途です。
具体例
Python の heapq は最小ヒープです。
import heapq
tasks = []
heapq.heappush(tasks, (3, "掃除"))
heapq.heappush(tasks, (1, "障害対応"))
heapq.heappush(tasks, (2, "<a href="/glossary/review" class="text-primary font-medium underline underline-offset-2 hover:text-primary-dark">レビュー</a>"))
print(heapq.heappop(tasks)) # (1, '障害対応') 優先度が最小のもの配列としての形は次のようになります。
1
/ 3 2 配列 [1, 3, 2, 7, 5]
/ 7 5
添字 i の親は (i-1)//2、子は 2i+1 と 2i+2似た用語との違い
| 語 | 何を指すか |
|---|---|
| ヒープ(データ構造) | 親子の大小を保つ木 |
| ヒープ領域 | 実行時に確保するメモリ領域 |
| スタック | 後に入れたものから取り出す構造 |
| 二分探索木 | 左右の大小まで決まっている木 |
名前は同じでも、メモリのヒープ領域とこの木構造は別物です。文脈で読み分けます。
つまずきやすいところ
ヒープの中身は整列済みではありません。heapq を使ったリストをそのまま表示すると順不同に見えますが、壊れているわけではなく、根だけが正しければよい構造です。
Python の heapq に最大ヒープはありません。値の符号を反転して入れるか、タプルの先頭にマイナスを付けた優先度を入れます。
タプルを入れる場合、優先度が同じだと 2 番目の要素で比較されます。比較できない型が 2 番目にあると例外になるため、間に通し番号を挟むのが定石です。
覚え方
「根だけは正しい」。全体は並んでいません。
