41

私はいくつかのオブジェクトのpriority_queueを持っています:

typedef priority_queue<Object> Queue;
Queue queue;

ときどき、オブジェクトの 1 つの優先度が変わることがあります。効率的な方法でキュー内のそのオブジェクトの優先度を更新できる必要があります。現在、私はこの方法を使用していますが、これは機能しますが非効率的です:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

当時はちょっと急いでいたので、この方法で実装しました。これが、問題なく動作することを確認できる最速の方法でした。ただし、これよりも良い方法があるはずです。本当に私が欲しいのは、次のいずれかの方法です。

  • 優先度が変更されたインスタンスを抽出し、新しい優先度値を持つ新しいインスタンスを挿入します
  • 変更された優先度でインスタンスを更新してから、正しくソートされるようにキューを更新します

これを行う最善の方法は何ですか？

4

7 に答える 7

61

どちらも実際の更新を実行しませんが、問題を解決するための 2 つの選択肢を提案できます。

  1. priority_queue更新するたびに and push 要素を使用します。キューに無駄なエントリがあるという事実を受け入れてください。最上位の値をポップするときは、最新の値が含まれているかどうかを確認してください。そうでない場合は、無視して次をポップします。

    このようにして、更新された要素が一番上に来るまで削除を遅らせます。このアプローチは、ダイクストラ アルゴリズムを実現するトップ プログラマーによって使用されていることに気付きました。

  2. を使用しsetます。また、対数時間で最大の要素を抽出できるように並べ替えられます。古い要素を再度挿入する前に削除することもできます。したがって、まだ更新操作はできませんが、取り外しと再挿入は実行可能です。

両方のアプローチの複雑さは同じようです。

于 2012-12-23T08:56:08.610 に答える
9

基になる deque/vector/list などにアクセスできないため、標準の優先度キューでは運が悪いと思います。独自のものを実装する必要があります - それほど難しくありません。

于 2009-03-16T09:09:38.583 に答える
5

適切なデータ構造は「フィボナッチ ヒープ」と呼ばれます。ただし、自分で実装する必要があります。挿入/更新は O(1) です ExtractMin は O(logn) です

于 2010-07-20T20:19:33.210 に答える
4

(私が知っている) STL でこれを行う最も簡単な方法は、エントリを削除し、その優先順位を更新してから、再度挿入することです。これは std::priority_queue を使用すると非常に遅くなりますが、std::set でも同じことができます。残念ながら、オブジェクトがセット内にある場合、オブジェクトの優先度を変更しないように注意する必要があります。

std::multimap (優先度から値へのマッピング用) と std::map (値から優先度へのマッピング用) を接着する mutable_priority_queue クラス ベースを実装しました。時間。コードと使用方法の例はこちらから入手できます

于 2010-02-06T21:34:20.440 に答える
0

ここreplace_ifで例を見てみたいと思うかもしれません。

于 2009-03-16T08:46:50.617 に答える
0

残念ながら、priority_queue の値を更新することはできません。priority_queue はそのようなインターフェースを提供しません。

setJarekczekが言ったように使用するか、このソリューションを使用する方がよいと思います（make_heapを使用）。

于 2017-01-02T01:06:44.577 に答える