ヒープと優先度付きキュー
01 / 共通の仕組み
ヒープを使えば極値(最小・最大)へ安価にアクセスでき、 残りはゆるい半順序のまま保てる。3 つのサブパターン:1 本のヒープで Top-K、 2 本のヒープでストリームの中央値、ソース指標を入れた最小ヒープで K 路マージ。
上から一つのサブパターンを選んでください。それぞれ単独でリンクできます — 問題に一番近いものから始めましょう。
↑ 選ぶ— / どれをいつ使うか
Top-K
完全な順序ではなく最も極端な k 個だけが必要なときに使う。
ストリーム · O(N log k) · LC 215 / 347 / 703
2 本のヒープ
ストリームの中央値を維持したいときに使う —— 下半分を最大ヒープ、上半分を最小ヒープに入れる。
中央値 · 最大ヒープ + 最小ヒープ · LC 295
K 路マージ
ソート済み列が K 本あり、全体の中から次に小さい要素を取り続けたいときに使う。
マージ · (val, src, idx) · LC 23 / 378