ヒープと優先度付きキュー
01 / 共通の仕組み
ヒープを使えば極値(最小・最大)へ安価にアクセスでき、 残りはゆるい半順序のまま保てる。3 つのサブパターン:1 本のヒープで Top-K、 2 本のヒープでストリームの中央値、ソース指標を入れた最小ヒープで K 路マージ。
01 / 一文での本質
K 本のソート済み列をマージするには、各列から 1 つずつエントリを入れた最小ヒープを保つ —— pop すれば全列を通しての次の最小値が得られ、1 要素あたりの代償は O(log K) だけ。
問題K 本のソート済みリストのマージK3リストL0=[1,4,7] L1=[2,5,9] L2=[3,6,8]
L0
1
4
7
L1
2
5
9
L2
3
6
8
ヒープ (value, src, idx)
—— 空 ——
out
·
3 本のソート済みリスト。最小ヒープに各リストの先頭を入れて種をまく —— ヒープには常に各ソース 1 件ずつのフロンティアが残る。
ステップ
0 / 22
|heap|
0
|out|
0
ヒープ最小
—
0 / 22
02 / パターンの骨格
# K 本のソート済みリストを 1 本にマージheap ← min-heap[ ] # key = (value, src, idx)for s in 0..K−1:if lists[s] not empty:heap.push((lists[s][0], s, 0))while heap not empty:(val, s, i) ← heap.pop()out.append(val)if i + 1 < |lists[s]|:heap.push((lists[s][i+1], s, i + 1))# タプル順:同値なら src、続いて idx —— 安定
03 / このパターンを使うべき合図
「K 本のソート済みリスト / ファイルのマージ」
最も典型的なシグナル。両端からの素朴な 2 本マージは
O(N · K) だが、 ヒープを使えば K 本のポインタを常に開いておくだけで O(N log K) に。「外部ソート」
メモリに入るチャンクをソートして書き出し、その後でチャンクをヒープでマージする —— データベースが RAM に収まらない表をソートする方法そのもの。
「複数の構造をまたぐ第 k 小」
ソート済み行列の第 k 小、2 つのソート済み配列の第 k 小和、 第 k 小のペア距離 —— いずれも K 路マージの変装。
「全リストを覆う最小区間」
各リストの先頭要素をヒープに 1 つずつ入れておく; ヒープの最小と現時点の全体最大の差が、候補となる区間幅。
04 / よくある落とし穴
i.
リスト全体を一気にヒープへ入れる。
ヒープを N ではなく K の大きさに保つことこそが要点。初期は各リストの先頭だけを push し、 pop のたびに該当ソースのポインタを 1 つずつ進める。さもなければ、 ただの
O(N log N) ソートを遠回りでやっているだけになる。ii.
タプルを忘れる —— キーには「どの列か」が必要。
ヒープに格納するのは
(value, src, idx)。 src がなければ pop 後にどのリストを進めればよいか分からない。 idx がなければ次の要素を取れない。両方を値と一緒に持ち運ぶ。iii.
同値で落ちる比較関数。
タプル順のヒープは同値時の順序を定義しておく必要がある —— 通常は src で。 Python の
heapq や Java の PriorityQueue<ListNode> など、 一部のライブラリは第 1 要素が同値だと第 2 要素を比較する。 第 2 要素が比較可能であるか、比較器を渡しておくこと。05 / LeetCode で練習
4 問。1 問目は定番の原型。中の 2 問は K 路マージの変装 —— ソート済み行列と 2 数の和。 最後は古典的な「最小区間」のバリエーション。
— / どれをいつ使うか
Top-K
完全な順序ではなく最も極端な k 個だけが必要なときに使う。
ストリーム · O(N log k) · LC 215 / 347 / 703
2 本のヒープ
ストリームの中央値を維持したいときに使う —— 下半分を最大ヒープ、上半分を最小ヒープに入れる。
中央値 · 最大ヒープ + 最小ヒープ · LC 295
K 路マージ
ソート済み列が K 本あり、全体の中から次に小さい要素を取り続けたいときに使う。
マージ · (val, src, idx) · LC 23 / 378