Geben Sie den höchsten Wert aus einer Prioritätswarteschlange ein, während Sie einige verwandte Knoten entfernen.

Question

Angenommen, wir haben eine Prioritätswarteschlange von n Knoten eines Graphen. Jedem Knoten wird ein Schlüssel zugewiesen, und alle Knoten werden basierend auf dem Schlüsselwert in der Prioritätswarteschlange sortiert.

Mit dem right implementation dauert das Abrufen des Kopfschlüssels (des Knotens mit dem höchsten Schlüsselwert) aus dieser Warteschlange O(log(n)).

Aber was ist, wenn es auch erforderlich ist, alle Fanouts und Fanins des Kopfknotens aus der Prioritätswarteschlange zu entfernen? Die offensichtliche Implementierung würde darin bestehen, alle Knoten in der Warteschlange zu durchsuchen, und wenn sie sich auf dem Kopf oder auf dem Kopf befinden, entfernen Sie sie. Dadurch wird die Laufzeit für POP O(nlog(n)).

Können wir es besser machen? Gibt es eine bessere Datenstruktur, die eine bessere Laufzeit bieten kann?

Answer 1

Grundsätzlich benötigen Sie eine Prioritätswarteschlange mit einem zusätzlichen löschen Betrieb. Um es effizient zu machen (das heißt, wenn Sie k Knoten aus der Warteschlange entfernen möchten, würde es O (k * log n) benötigen), benötigen Sie ein Handle auf den Knoten.

Ein übliches Verfahren ist ein Array, das die ID eines Eckpunkts mit dem Knoten in der Prioritätswarteschlange verknüpft. Dann hängt der Löschalgorithmus davon ab, welche Prioritätswarteschlange implementiert ist.

Ich glaube nicht, dass Sie in Bezug auf die Leistung besser sein können, weil die andere Lösung, die darin besteht, ein sortiertes Array zu verwalten, teurer ist (muss das Array für jede Änderung sortiert halten).

Answer 2

Erstellen Sie beim Erstellen Ihrer Prioritätswarteschlange eine Hashtabelle, die für jeden Knoten die Position im Array enthält, das zum Hosten der Prioritätswarteschlange verwendet wird. Wenn Sie die Prioritätswarteschlange ändern, führen Sie dies in der Regel durch, indem Sie zwei Elemente im Array austauschen. Jedes Mal, wenn Sie dies tun, aktualisieren Sie die Werte in der Hashtabelle, so dass sie immer noch den korrekten Offset im Array der Prioritätswarteschlange für jeden Knoten enthält. Dies ist nur ein konstanter Zeitaufwand für die Operationen, die die Prioritätswarteschlange implementieren.

Jetzt müssen Sie Code schreiben, um einen beliebigen Knoten aufzunehmen, seinen Offset in der Prioritätswarteschlange aus der Hashtabelle zu lesen, das Element an diesem Offset aus dem Prioritätswarteschlangenfeld zu entfernen und dann den Knoten und zu entfernen der zugehörige Wert aus der Hash-Tabelle.

Die einzige knifflige Sache ist, ein Element aus einer beliebigen Position im Priority-Queue-Array (die ich für einen Heap halte) zu entfernen und die Invarianten des Heaps wiederherzustellen. Jedes Element hat höchstens einen Elternteil und höchstens zwei Kinder. Unter der Annahme, dass die höchste Priorität oben ist, muss jedes Element nicht höher als sein Elternteil und mindestens so hoch wie eines seiner Kinder sein. Wenn Sie jetzt das Element mit dem größten gültigen Array-Index mit dem Element austauschen, das Sie entfernen, kann der Schlüssel entweder zu- oder abnehmen, sodass Sie einen dieser beiden Invarianten, aber nicht beide, auflösen können.

Wenn das Element jetzt größer ist als das übergeordnete Element, verwenden Sie das standardmäßige heap-invariante Fixup, das sich zum Anfang des Heapspeichers bewegt. Dies kann nur die Schlüssel in den Elementen, die es verdrängt, erhöhen. Wenn es beendet ist, werden die Heap-Invarianten wiederhergestellt. Wenn das Element nun kleiner als eines seiner Kinder ist (wahrscheinlicher), tauscht man es gegen das größere der beiden Kinder und fährt wie gewohnt weiter.

In beiden Fällen ist dies ein Standard-Heap-Sichten oder Sieben (mit der zusätzlichen Buchhaltung, um die Hash-Tabelle auf dem neuesten Stand zu halten), so dass die Kosten O (log n) sind).

(Alternativ verwenden Sie keine Prioritätswarteschlange, sondern eine Datenstruktur wie eine Java TreeMap oder TreeSet, die ein assoziatives Array mit einer Operation ist, mit der Sie das Element im Array mit dem größten (oder Kleinster) Schlüssel in diesem Fall haben Sie sehr wenig zu implementieren, und jede Operation ist immer noch O (log n).