ヒープと優先度付きキュー
01 / 共通の仕組み
ヒープを使えば極値(最小・最大)へ安価にアクセスでき、 残りはゆるい半順序のまま保てる。3 つのサブパターン:1 本のヒープで Top-K、 2 本のヒープでストリームの中央値、ソース指標を入れた最小ヒープで K 路マージ。
01 / 一文での本質
N 個の中から最も極端な k 個を追うには、サイズ k のヒープを保ち、 その根を k 個のうちで最も劣るものにしておく —— 新しい要素は根を追い出すか、追い出さないかのどちらか。
問題ストリームから上位 k 個ストリーム[3, 1, 5, 12, 2, 11, 7, 8]k3
ストリーム
30
11
52
123
24
115
76
87
—— ヒープは空 ——
heap = [ ]
サイズ k = 3 の最小ヒープを保つ。根は上位 k のうちで最小 —— 厳密に大きい新要素だけが根を追い出す。
ステップ
0 / 17
ヒープサイズ
0
最小(根)
—
動作
init
0 / 17
02 / パターンの骨格
# 上位 k 個 —— サイズ k の最小ヒープheap ← [ ]for x in stream:if |heap| < k:heap.push(x)elif x > heap[0]:heap.replace_root(x)return sort(heap, descending)# 下位 k 個:最大ヒープに替え、比較を逆にする
03 / このパターンを使うべき合図
「上位 k / 第 k」
欲しいのは最も極端な k 個であって、完全な順序ではない。 要は
O(N log N) 未満で済ませること。「ストリーミング / オンライン」
要素は 1 つずつ届き、全体を一度に見ることはできない。 サイズ k のヒープなら、ストリームの長さに関わらず一定メモリで答えを返せる。
「頻度 / 重み付き」
「極端」が指すのは生の値ではなく、出現回数や距離など派生したキー。 アルゴリズムは同じ、比較関数だけが違う。
「分位数 / 第 k 大」
ウィンドウやストリームにおける第 k 大は、サイズ k のヒープが自然に保持する量そのもの。 ストリームの中央値が必要ならヒープを 2 本使う —— two-heaps を参照。
04 / よくある落とし穴
i.
最大を見つけるのに最大ヒープを使う。
上位 k 個の最大には、サイズ k の最小ヒープを使う —— 根は残す k 個の中で最小であり、より大きな新要素がそれを追い出す。 サイズ k の最大ヒープでは見たうちの最大値が頂点に来てしまい、 第 k 大を安価に確認できなくなる。
ii.
置換時に厳密
> か非厳密 ≥ か。厳密
> なら、根と等しい新要素は拒否される —— 既存の重複はそのまま残る。≥ なら入れ替わって入る。重複のない入力では結果は同じだが、 重複があるときには違いが出る。問題に合わせて選ぶこと。iii.
ソートで十分なときにまでヒープを持ち出す。
N 要素がすべてメモリにあり、k が N に近いなら、ソートのほうが単純で性能も互角。 ヒープが勝つのは N ≫ k のとき、あるいはストリーミングで全部を保持できないとき。
05 / LeetCode で練習
4 問。1 問目は定番の「第 k 大」。2 問目は頻度をキーに使う —— アルゴリズムは同じ、比較器が違う。 3 問目はストリーミング設定を強調する。4 問目はヒープと貪欲選択を組み合わせた古典的応用。
— / どれをいつ使うか
Top-K
完全な順序ではなく最も極端な k 個だけが必要なときに使う。
ストリーム · O(N log k) · LC 215 / 347 / 703
2 本のヒープ
ストリームの中央値を維持したいときに使う —— 下半分を最大ヒープ、上半分を最小ヒープに入れる。
中央値 · 最大ヒープ + 最小ヒープ · LC 295
K 路マージ
ソート済み列が K 本あり、全体の中から次に小さい要素を取り続けたいときに使う。
マージ · (val, src, idx) · LC 23 / 378