c++ - priority_queue から一番上にない要素を削除するには?

Question

私のプログラムでは、一番上にない優先キューから要素を削除する必要があります。それはできますか？そうでない場合は、独自のヒープを作成する以外の方法を提案してください。

Answer 1

Pradip と MASh は、削除操作を実現するために時間を犠牲にします。ただし、時間の複雑さが重要な場合は、ハッシュ min_heap を使用することをお勧めします。ハッシュ テーブルには値ポインターが格納され、ポインターは min_heap を指します。つまり、min_heap の値を見つけるのに O(1) 時間を費やし、O(log(n)) を使って要素を削除 (ふるいにかけるか、ふるいにかける) できるということです。

Answer 2

次のアプローチは問題を解決しますが、ソリューションへの最適化された方法ではないことに注意してください。最適化されたアプローチについては、他の回答を確認してください。

の 5 番目の要素を削除しますpriority_queue<type> Q。次に、次のようにできます。

vector<type> tempQ;
int i = 0;
int n = 5;
type t;

// backup n-1 items
while(i < n-1)
{
    tempQ.push_back(Q.top());
    Q.pop();        
    i++;
}

// remove the nth item
Q.pop();

// restore the backed up items
i = 0;
while(i < n-1)
{
    t = tempQ[i++];
    Q.push(t);
}