Wie eine effiziente Priorität Update in STL priority_queue zu tun?

Question

Ich habe eine priority_queue eines Objekts:

typedef priority_queue<Object> Queue;
Queue queue;

Von Zeit zu Zeit, die Priorität eines der Objekte ändern kann - ich brauche die Priorität dieses Objekts in der Warteschlange auf eine effiziente Art und Weise aktualisieren zu können. Derzeit bin ich mit dieser Methode, die funktioniert, aber scheint ineffizient:

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

ich es auf diese Art und Weise umgesetzt, weil ich in der Art von Eile zu der Zeit war, und das war das schnellste, was ich tun könnte, dass ich sicher sein konnte, ist es ok funktionieren würde. Es muss ein besserer Weg, als dies, obwohl sein. Wirklich, was ich will, ist ein Weg, um entweder:

• extrahieren Sie die Instanz mit der geänderten Priorität und eine neue mit dem neuen Prioritätswert einfügen
• aktualisieren die Instanz mit der geänderten Priorität und dann die Warteschlange aktualisieren, so dass es richtig sortiert ist

Was ist der beste Weg, dies zu tun?

Answer 1

Ich denke, man Pech mit Standard-Prioritätswarteschlange ist, weil Sie nicht an der zugrunde liegenden deque / Vektor / Liste oder was auch immer bekommen. Sie müssen Ihre eigenen implementieren - es ist nicht so schwer,

.

Answer 2

Ich kann die Wahl zwischen 2 legen nahe, das Problem zu lösen, obwohl weder ein echtes Update durchführt.

1. die priority_queue verwenden und drücken Sie jedes Mal Element Sie es aktualisieren möchten. Akzeptieren Sie die Tatsache, dass Sie nutzlos Einträge in der Warteschlange haben. Wenn die obere Wert Knallen, überprüfen, ob es die up-to-date-Wert enthält. Wenn nicht, ignorieren sie und Pop die nächste.

   Auf diese Weise kann die Entfernung des aktualisierten Elements verzögern, bis es an die Spitze kommt. Ich bemerkte, diesen Ansatz von Top-Programmierern verwendet wird Realisierung Dijkstra-Algorithmus.

2. Mit set. Es ist auch so dass Sie das größte Element in logarithmischer Zeit zu extrahieren, sind in der Lage sortiert. Sie sind auch vor dem veraltete Element entfernen, können Sie sie wieder einführen. So noch kein Update Betrieb möglich, aber Entfernen und Wiedereinsetzen ist machbar.

Scheint, wie die Komplexität beiden Ansätze sind das gleiche.

Answer 3

Der einfachste Weg, dies mit STL zu tun (die ich kenne) ist es, den Eintrag zu entfernen, seine Priorität zu aktualisieren und dann wieder ein. Dadurch ist ziemlich langsam std :: priority_queue verwenden, jedoch können Sie das Gleiche mit std :: tun gesetzt. Leider muss man vorsichtig sein, um nicht die Priorität eines Objekts zu ändern, wenn es in der Gruppe ist.

Ich habe eine mutable_priority_queue Klasse basiert Kleben zusammen eine std :: realisiert multimap (für die Priorität der Werte-Mapping) und eine std :: map (zum Wert der Priorität Mapping), die Sie Artikel sowie Update einfügen können / entfernen bestehende Werte in logarithmischer Zeit. Sie können den Code bekommen und ein Beispiel dafür, wie es zu benutzen hier

Answer 4

Die entsprechende Datenstruktur „Fibonacci-Heap“ bezeichnet. Aber Sie müssen es selbst implementieren. Insert / Updates sind O (1) ExtractMin ist O (log n)

Answer 5

Ich habe eine High-Performance-aktualisierbar Prioritätswarteschlange implementiert und zugänglich gemacht auf Github .

Dies ist, wie Sie würde es in der Regel verwenden:

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

Um Jarekczek Antwort zu ergänzen, wenn in die Tat sowohl die set und „reiner Haufen mit nutzlosen Einträgen“ Ansätze haben die gleiche Komplexität, die stl::set Version führt typischerweise viel langsamer als die stl::priority_queue Version aufgrund der Tatsache, dass es mit rot-schwarz umgesetzt wird Bäume, die nur ihre Tiefe garantieren, dass sie niedriger als 2 * log_2 (n_elements) und erfordern regelmäßige Updates, während stl::priority_queue ein so rein und schnelle binäre Haufen wie möglich ist. Aus diesem Grunde ist es in der Regel verwendet, wenn Dijkstra implementieren.

Der Satz Ansatz kann jedoch schneller sein, wenn viele Updates auf wenige Basisknoten zu machen. Das ist auch, wo meine Bibliothek würden Sie die meisten Verbesserung bringen.

Answer 6

Sie können einen Blick auf replace_if mit einem Beispiel haben wollen hier .

Answer 7

Leider kann man nicht Wert in priority_queue aktualisieren. priority_queue nicht solche Schnittstelle bieten.

Ich glaube, Sie besser set verwenden würde, wie Jarekczek gesagt oder diese Lösung (mit make_heap) verwenden.