次の操作ができる優先度つきキューのおはなしです。
push(x)：xを挿入するpop_newest(k)：挿入順が新しい方から k 以内の要素の最大値を取得・削除pop_oldest(k)：挿入順が古い方から k 以内の要素の最大値を取得・削除- 取得だけする
peek_newest(k),peek_oldest(k)もできる
- 取得だけする
pop()：最大値を取得・削除- これは
pop_newest(oo)でできる ooは \(\infty\) のこと
- これは
計算量は amortized \(O(\log(n))\) time です。\(n\) はその時点での要素数です。
記事の構成は以下の流れになります。
- 優先度つきキューを実装してみる
- よくある二分ヒープとは異なるアプローチ
- の実装から自然に
pop_newest(k)などを捌けるので、その説明をする
- の実装から自然に
- 同じアイディアで他のデータ構造も作れるので、その紹介をする
優先度つきキューの実装
区間最大値を取得できるデータ構造としてセグ木がありますね。セグ木を使って優先度つきキューを作ります。
大まかなアイディアとしては次の通りです。
- 長さ \(m\) のセグ木 \(a\) を用意し、添字 \(i \gets 0\) で初期化する。
push(x)の際は、\(a_i \gets x\), \(i\gets i+1\) で更新する。pop()の際は、全体の最大値 \(a_j\) を取得し、\(a_j\gets-\infty\) で更新する。
\(a_j\) を更新するために \(j\) が必要になりますが、以下のふたつの方法があります。
- まず最大値 \(x\) を求めて、\([0, j+1)\) の最大値が \(x\) になるような \(j\) の最小値を二分探索で求める
- \( (a_i, i)\) のペアの辞書順 max を返す演算をセグ木に乗せる
ほぼできていますが、次の問題点があります*1。
- \(m+1\) 回の挿入をしようとするとこわれる
- 要素数 \(n\) に対する log ではなく、決め打ちしたサイズ \(m\) に対する log の時間になる
これは適当に解決できます。 \(i=m\) で挿入しようとした場合と、\(n\le m/4\) で削除しようとした場合*2に、再構築します。
セグ木のサイズを \(m\gets 2n\) で更新し、元々の \(-\infty\) 以外の要素を前半に詰め直します。残りは \(-\infty\) でうめます*3。
ならし計算量解析のよくある議論（vector を適切なタイミングで伸縮させるやつ）と同じような議論で、再構築のコストが \(O(1)\) 時間であることが言えるはずです。再構築のおかげで \(m=O(n)\) になるので、amortized \(O(\log(n))\) time となります。
古い方から \(k\) 個以内のやつの処理
区間和のセグ木を用意します。これを \(b\) とします。 各 \(i\) に対して、\(a_i \gt -\infty\) のとき \(b_i = 1\)、そうでないとき \(b_i = 0\) とします。
セグ木 \(b\) 上の二分探索で「\([0, i)\) が区間和が \(k\) となる最小の \(i\)」を求め、その \(i\) に対して \(a\) で \([0, i)\) の区間 max を求めます。
新しい方から \(k\) 個以内についても似た感じです。 \(b\) 上の二分探索を 2 回やれば、挿入順が \([k_L, k_R)\) の max とかもできます。
他のデータ構造
上記と同様のアイディアで、次の操作が amortized \(O(\log(n))\) time でできます。
push(x)：末尾にxを追加remove(i)：i番目の要素を削除fold(l..r)：区間l..rのモノイド積を求める- あるいは
[i]：添字iの要素の取得
- あるいは
上記で \(-\infty\) を詰めていた箇所の代わりには、単位元 \(e\) を使えばよいです。 こっちの方がむしろよく見るかもしれませんね。
あとがき
なんか疲れていて、直近 \(k\) 個以内の最大値を取得できるヒープがあれば面白そうでは？と思った日があったので書きました。 応用例があるのかはわかりません。
区間モノイド積を求められる平衡木でも当然できます。
おわり
お粗末さまでした。
