8

priority_queueがあり、その内容の一部（優先度値）を変更したいのですが、キューは再利用されますか？

それがプッシュ/ポップに頼るか（より可能性が高いのは、全体に頼るのではなく、単に「挿入」する必要があるため）、またはトップまたはポップにアクセスするかどうかによって異なります。

キュー内のいくつかの要素を本当に変更したいです。そんな感じ：

priority_queue<int> q;

int a=2,b=3,c=5;
int *ca=&a, *cb=&b, cc=&c;

q.push(a);
q.push(b);
q.push(c); //q is now {2,3,5}

*ca=4;

//what happens to q?
// 1) {3,4,5}
// 2) {4,2,5}
// 3) crash
4

4 に答える 4

4

priority_queueプッシュした値をコピーします。最後の割り当ては、優先キューの順序にも、その中に格納されている値にも影響を与えません。

于 2012-12-24T01:45:20.113 に答える
4

残念ながら、std::priority_queueクラスはincrease/decrease_keyあなたが探している操作をサポートしていません。もちろん、更新するヒープ内の要素を見つけて、呼び出してバイナリヒープの不変条件を復元することは可能ですが、これは、コンテナー/アルゴリズムmake_heapの場合ほど効率的に行うことはできません。std::ヒープをスキャンしてアイテムを見つけるO(N)と、その上にmake_heapあります。更新を適切にサポートするバイナリヒープを探すO(N)ことができるはずです。increase/decrease_keyO(log(N))

Boostは、優先キューの実装のセットを提供します。これは、（ペアリングヒープ、フィボナッチヒープなど）よりも効率的であり、std::priority_queue可変性も提供するため、動的な更新を効率的に実行できます。したがって、すべてのラウンドで、ブーストコンテナを使用する方がはるかに優れたオプションになる可能性があります。

于 2012-12-24T02:11:34.820 に答える
2

さて、少し検索した後、キューを「並べ替える」方法を見つけたので、優先度の値を変更するたびに、次の呼び出しを行う必要があります。

std::make_heap(const_cast<Type**>(&queue.top()),
     const_cast<Type**>(&queue.top()) + queue.size(),
     ComparerClass());

そしてキューはその時でなければなりません

std::priority_queue<Type*,vector<Type*>,ComparerClass> queue;

お役に立てれば。

于 2012-12-24T02:14:11.510 に答える
2

A *アルゴリズムに優先度付きキューを使用することを検討しているときに、この問題に遭遇しました。

基本的に、C++優先キューは非常に限られたおもちゃです。

キューに入れられた要素の優先度を動的に変更するには、基になるヒープの完全な再構築を手動で実行する必要があります。これは、特定のSTL実装で機能することが保証されておらず、非常に非効率的です。
さらに、ヒープを再構築するには、お尻の醜いコードが必要です。これは、さらに別の難読化されたクラス/テンプレートに隠す必要があります。

C ++の他の多くのものについては、車輪の再発明を行うか、それを再発明したファッショナブルなライブラリを見つける必要があります。

于 2014-09-14T20:52:50.563 に答える