ヒープと優先度付きキュー
01 / 共通の仕組み
ヒープを使えば極値(最小・最大)へ安価にアクセスでき、 残りはゆるい半順序のまま保てる。3 つのサブパターン:1 本のヒープで Top-K、 2 本のヒープでストリームの中央値、ソース指標を入れた最小ヒープで K 路マージ。
02 / 一文で言うと
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
03 / パターンの骨格
# 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 —— 安定
04 / このパターンを使うべき合図
「K 本のソート済みリスト / ファイルのマージ」
最も典型的なシグナル。両端からの素朴な 2 本マージは
O(N · K) だが、 ヒープを使えば K 本のポインタを常に開いておくだけで O(N log K) に。「外部ソート」
メモリに入るチャンクをソートして書き出し、その後でチャンクをヒープでマージする —— データベースが RAM に収まらない表をソートする方法そのもの。
「複数の構造をまたぐ第 k 小」
ソート済み行列の第 k 小、2 つのソート済み配列の第 k 小和、 第 k 小のペア距離 —— いずれも K 路マージの変装。
「全リストを覆う最小区間」
各リストの先頭要素をヒープに 1 つずつ入れておく; ヒープの最小と現時点の全体最大の差が、候補となる区間幅。
05 / よくある落とし穴
リスト全体を一気にヒープへ入れる。
ヒープを N ではなく K の大きさに保つことこそが要点。初期は各リストの先頭だけを push し、 pop のたびに該当ソースのポインタを 1 つずつ進める。さもなければ、 ただの
O(N log N) ソートを遠回りでやっているだけになる。タプルを忘れる —— キーには「どの列か」が必要。
ヒープに格納するのは
(value, src, idx)。 src がなければ pop 後にどのリストを進めればよいか分からない。 idx がなければ次の要素を取れない。両方を値と一緒に持ち運ぶ。同値で落ちる比較関数。
タプル順のヒープは同値時の順序を定義しておく必要がある —— 通常は src で。 Python の
heapq や Java の PriorityQueue<ListNode> など、 一部のライブラリは第 1 要素が同値だと第 2 要素を比較する。 第 2 要素が比較可能であるか、比較器を渡しておくこと。06 / LeetCode で練習
中級11
01Sort List— LC 148→02Ugly Number II— LC 264→03Super Ugly Number— LC 313→04Find K Pairs with Smallest Sums— LC 373→05Kth Smallest Element in a Sorted Matrix— LC 378→06K-th Smallest Prime Fraction— LC 786→07Minimum Cost to Connect Sticks— LC 1167→08Path With Minimum Effort— LC 1631→09Single-Threaded CPU— LC 1834→10Divide Intervals Into Minimum Number of Groups— LC 2406→11Maximal Score After Applying K Operations— LC 2530→
難しい8
01Merge k Sorted Lists— LC 23→02Find Median from Data Stream— LC 295→03IPO— LC 502→04Smallest Range Covering Elements from K Lists— LC 632→05Kth Smallest Number in Multiplication Table— LC 668→06Find K-th Smallest Pair Distance— LC 719→07Minimize Deviation in Array— LC 1675→08Find the K-Sum of an Array— LC 2386→
— / どれをいつ使うか
Top-K
完全な順序ではなく最も極端な k 個だけが必要なときに使う。
ストリーム · O(N log k) · LC 215 / 347 / 703
2 本のヒープ
ストリームの中央値を維持したいときに使う —— 下半分を最大ヒープ、上半分を最小ヒープに入れる。
中央値 · 最大ヒープ + 最小ヒープ · LC 295
K 路マージ
ソート済み列が K 本あり、全体の中から次に小さい要素を取り続けたいときに使う。
マージ · (val, src, idx) · LC 23 / 378