機能に合わせたデータ構造

挿入したデータの中から、優先度順にデータを取り出すデータ構造を、優先度付き待ち行列という。
これはヒープ構造を用いると、効果的に実装が可能である。
　
今、、、優先度付き待ち行列に「優先度が一定値より低いものは全て要らないから、棄ててしまって」という機能を追加したい。
さて、どんなデータ構造を用いて、機能を満たす優先度付き待ち行列を実装するのが、最も良いか？
　
データ構造に既に入ってる要素数をNとして…
挿入　→　O(logN)
取り出し　→　O(logN)
一定値以下の切捨て　→　O(？？)
　
さて、、、？？部分がどうなるのか？　って問題ですね。
　
挿入と取り出しが両方O(logN)なデータ構造として思い浮かぶのは、木構造だと思います。
バランス木辺りを使えば、良いんじゃね？　2分木でも良いけど？　とか。
これ、メモリ開放しなくて良い（メモリリークして良い）なら、一定値以下の切捨てもO(logN)で出来てしまいます。
しかしメモリ開放しないわけにはいかないので、結局のところO(NlogN)になってしまいます。
まぁ、ガベコレの実装次第では、O(logN)で出来そうな気がしないでもないです。
（※Javaとかのガベコレだと、遅延した解放処理で結局のところO(N)って感じかな？）
（ノードにデストラクタがある時点でO(N)は避けられないんだけど……）
（ノードにデストラクタがなくて、確保単位で解放を行わないようなガベコレがあればO(logN)になる可能性がゼロではないということね……厳密にそれを満たすガベコレがあるかどうかは知らないけど……もしあったとして、ガベコレのコストが半端なく大きそうな気はするけれども）
　
まぁ今回書いてるのはC++なんで、とりあえず条件を満たす様なガベコレは手元に無いです。
だったら、別に、ヒープ壊して、一定値以下を切り捨てて、ヒープ構造を再構築してもO(NlogN)なんじゃね？
ってわけですね。
　
まぁ、実際にはオーダーだけで全てを語るわけにはいかないので何とも言えないんですが……
複雑な木構造を使うよりも、単純なヒープ構造を使った実装の方が、速度の出せる実装が可能なんじゃないかなとか。
　
ちなみに、これをソート済み環状配列で実装すると……
挿入　→　O(N)
取り出し　→　O(1)
一定値以下の切捨て　→　O(logN)
となるかな、たぶん。
　
そういえば、メモリのいたるところに空きのあるヒープ的なメモリ配置の2分木なら、ガベコレもなしにO(logN)で、一定値以下の切捨てが……だめだ、最悪で2^Nのメモリが必要になる。
　
というわけで、テキトーに実装してきます。
（この日記自体、テキトーに書かれているので、現実との間にギャップがあるかもしれません。ご了承ください）