ヒープと優先度付きキュー
01 / 共通の仕組み
ヒープを使えば極値(最小・最大)へ安価にアクセスでき、 残りはゆるい半順序のまま保てる。3 つのサブパターン:1 本のヒープで Top-K、 2 本のヒープでストリームの中央値、ソース指標を入れた最小ヒープで K 路マージ。
01 / 一文での本質
ストリームを 2 つに分ける:最大ヒープに下半分、最小ヒープに上半分。両者のサイズをつねに均衡させれば、 中央値は必ずどちらかの根にある。
問題ストリームのオンライン中央値ストリーム[5, 2, 8, 1, 9, 3, 7]
ストリーム
50
21
82
13
94
35
76
low —— 最大ヒープ
—— 空 ——
low = [ ]
high —— 最小ヒープ
—— 空 ——
high = [ ]
中央値—
2 本のヒープ:左の最大ヒープに下半分、右の最小ヒープに上半分。中央値はその境界に住む。
ステップ
0 / 28
|low|
0
|high|
0
中央値
—
0 / 28
02 / パターンの骨格
# 2 本のヒープ —— low は最大ヒープ、high は最小ヒープlow、high ← max-heap[ ]、min-heap[ ]for x in stream:if low.empty() or x ≤ low.top():low.push(x)else: high.push(x)# |low| − |high| ∈ {0, 1} となるよう再均衡if |low| > |high| + 1: high.push(low.pop())elif |high| > |low|: low.push(high.pop())median ← |low| > |high| ? low.top() : (low.top() + high.top()) / 2
03 / このパターンを使うべき合図
「ストリームの中央値」
最も典型的なシグナル。数値が 1 つずつ届き、各挿入のたびに中央値を答える必要がある。 毎回ソートすると 1 ステップあたり O(N) になるが、2 本のヒープなら O(log N)。
「スライディングウィンドウ中央値」
同じ仕組みに、ウィンドウから出る要素の遅延削除を加える —— 多くの場合「保留中の削除」を保持するハッシュマップを用意し、各根アクセス時に掃除する。
「上下 2 つに分ける」
解が「x より小さい部分」と「x より大きい部分」の境界で決まる問題はすべてこの発想で見られる —— 医師のスケジューリング、負荷分散、2 つのソート済み配列の中央値など。
「下半分の和 / 平均」
下半分を保持する最大ヒープ自体が有用な対象。そのサイズと総和から、 最小 k 個の平均がそのまま得られる。
04 / よくある落とし穴
i.
挿入のたびに再均衡を忘れる。
サイズ不変条件
|low| − |high| ∈ {0, 1} は、即時に直してこそ保たれる。 再均衡を 1 回でも飛ばすと、それ以降の中央値はずっと誤ったヒープから読まれることになる。ii.
値ではなくサイズでどちらに挿入するか決めてしまう。
現在の low の根との比較こそが、分割の順序を保つ要。 小さい方のヒープに無条件で入れると、不変条件
max(low) ≤ min(high) が崩れ、中央値が誤る。iii.
偶数サイズの中央値で整数オーバーフロー / 境界 1 ずれ。
両ヒープが同サイズのとき、中央値は
(low.top() + high.top()) / 2。 整数型では和がオーバーフローしうる。より広い型で計算する (あるいは low.top() + (high.top() − low.top()) / 2 に偶奇補正を加える)。05 / LeetCode で練習
4 問。1 問目は定番の原型。次の 2 問はスライディングウィンドウと移動平均を加える。 最後はぱっと見は無関係で、内部は 2 本のヒープでとける古典問題。
— / どれをいつ使うか
Top-K
完全な順序ではなく最も極端な k 個だけが必要なときに使う。
ストリーム · O(N log k) · LC 215 / 347 / 703
2 本のヒープ
ストリームの中央値を維持したいときに使う —— 下半分を最大ヒープ、上半分を最小ヒープに入れる。
中央値 · 最大ヒープ + 最小ヒープ · LC 295
K 路マージ
ソート済み列が K 本あり、全体の中から次に小さい要素を取り続けたいときに使う。
マージ · (val, src, idx) · LC 23 / 378