c++ - std::priority_queue の縮小

Question

std::priority_queue を指定すると、最適な要素を繰り返しポップする通常のプロセスによって要素が削除されるよりも速く追加されるため、何かが行われない限り、プログラムはメモリを使い果たします。

要素の最悪の半分を捨て、最良の半分を通常どおり一度に 1 つずつ処理する方法はありますか?

Answer 1

直接的な方法はありません。しかし、とにかく、バイナリ ヒープは実際にはその操作をサポートしていません。

しかし、間接的にそうするのは難しくありません:

• 一時的な空のプライオリティ キューを作成する
• メイン キューと一時キューを入れ替える
• 一時からポップしてメインにプッシュするループに入る
• コピーされた要素の数に満足したら停止します
• 一時キューを破棄します。

Answer 2

std::priority_queue へのインターフェースは非常に限られているため、明らかにそうではありません。make_heap、push_heap、pop_heap (これが std::priority_queue の実装方法です) を使用してこれを行う独自の優先度キューを実装し、要素の最悪の半分を削除する独自の関数を実装できます。

Answer 3

はstd::priority_queue2 ヒープであるため、部分的にしか順序付けされていません。データ構造は、要素を抽出するのとは異なり、要素の最良の半分を見つけるのに役立ちません。