概要
std::priority_queue (binary heap) を つ持って、片方には削除待ちの要素を入れることで、実質的に削除ができるようにするテクニックがある。
ただし、これは invalid な削除も可能になってしまう。
つまり、存在しない要素
を削除する操作をした後に
を挿入すると、場合によってはこの
が消えてしまうことがある。
これを不可能にする方法を考察してみた。
方法 
std::unordered_(multi)set(map) (hashset) あるいはより高速な自作の hashset を使って、要素が存在するかどうか管理し、invalid な削除を弾く。
利点
invalid になり得る削除をしたい場面では、削除が成功したかも同時に必要になることが多い気がする。
この場合 pop を呼ばなければ hashset と全く同じ操作になるので、結局 hashset は必要になる。
上手く実装された hashset は高速で、binary heap の と比較するとボトルネックにはならない気がする。
欠点
その型に対して hash 関数が定義されている必要がある。
速度を気にするなら、その hash 関数の計算時間と散らばりにも気を配らなくてはいけない。
std::unordered_set は遅かった気がするので、これを避けるなら自作 hashset が必要になり、面倒。
方法 
挿入した要素と削除待ちの要素に、それぞれの操作が行われた時刻を記録する。 挿入より早く削除されていた場合、その削除は無視する。 より厳密には、以下のようなアルゴリズムを使う。
- クエリ呼び出しの度にインクリメントすることで、時刻を管理する。
- 削除クエリの度に、以下の操作を繰り返し行う。
topを見る。- 削除側の方が priority が高い、または priority が等しいが削除側の方が時刻が早いなら、削除側だけ
popする。 - 両者の priority が等しく、削除側の方が時刻が遅いなら、両方同時に
popする。 - 削除側の方が priority が低い、またはどちらかが空になったら終了する。
正当性
「本体の heap と削除側の heap の要素を時刻順に並べてその通りにクエリを処理すると、真の heap の要素が得られる」という不変条件を維持していることを確認せよ。
繰り返しが終了したとき、本体の heap の top は真の heap の top と一致している。
利点
簡単に書ける。
欠点
key が つの要素の対になったので、比較に時間がかかり、遅くなる。
計測していないが、
std::set を利用するより遅くなっていたら実用性は無になる。
priority が大きくない整数なら、 などを key にすれば比較は高速になるかもしれない。
