Position Index für binäre Heap-Prioritätswarteschlangen?

Question

Angenommen, ich habe eine Prioritätswarteschlange von N Elementen mit Prioritäten, wobei N in den Tausenden liegt, die eine Prioritätswarteschlange verwenden, die mit einem Binärhaufen implementiert ist. Ich verstehe die EXTRACT-MIN und INSERT Primitiven (siehe Cormen, Leiserson, Rivest, die -MAX anstelle von -MIN verwenden).

Aber DELETE und DECREASE-KEY scheinen beide zu erfordern, dass die Prioritätswarteschlange in der Lage ist, den Index eines Elements im Haufen anhand des Elements selbst zu finden (alternativ muss dieser Index von den Verbrauchern der Prioritätswarteschlange gegeben werden, aber das scheint wie ein Verstoß gegen die Abstraktion).... was wie ein Versäumnis aussieht. Gibt es eine Möglichkeit, dies effizient zu tun, ohne eine Hashtabelle oben auf den Haufen hinzufügen zu müssen?

Answer 1

Richtig, ich glaube der Punkt hier ist, dass für die Implementierung der Prioritätswarteschlange können Sie einen Binärhaufen verwenden, dessen API einen Index (i) für sein HEAP-INCREASE-KEY(A, i, Schlüssel) erfordert, aber die Schnittstelle zur Prioritätswarteschlange darf einen beliebigen Schlüssel akzeptieren. Sie können die Prioritätswarteschlange frei die Details von Schlüssel->Index-Abbildungen umschließen lassen. Wenn Sie möchten, dass Ihr PQ-INCREASE-KEY (A, alt, neu) in O(log n) funktioniert, dann sollten Sie eine O(log n) oder bessere Schlüssel-zu-Index-Suche haben, die Sie aktuell halten. Das könnte eine Hashtabelle oder eine andere schnelle Suchstruktur sein.

Also, um Ihre Frage zu beantworten: Ich glaube, es ist unvermeidlich, dass die Datenstruktur irgendwie erweitert wird.

Answer 2

Übrigens, und falls jemand immer noch nach etwas Ähnlichem sucht – ich stieß kürzlich auf eine Implementierung für eine indizierte Prioritätswarteschlange, während ich einen der Coursera-Kurse zu Algorithmen machte.

Die Grundidee besteht darin, einen Reverse-Lookup mithilfe von 2 Arrays einzubinden, um die vom Ersteller angegebenen Operationen zu unterstützen.

Hier ist eine klare Implementierung für geordnete indizierte Prioritätswarteschlange.

Answer 3

Ich habe meine Knotenklasse geändert, um ein heapIndex-Mitglied hinzuzufügen. Dies wird vom Heap verwaltet, wenn Knoten während des Einfügens, Löschens, Verringerungen usw. ausgetauscht werden.

Dies bricht die Kapselung (meine Knoten sind nun an den Heap gebunden), aber es läuft schnell, was in meiner Situation wichtiger war.

Answer 4

Ein Weg ist, den Heap in die Elemente auf der einen Seite und die Organisation auf der anderen Seite aufzuteilen.

Für volle Funktionalität benötigen Sie zwei Beziehungen: a) Gegeben ein Heap-Standort (z. B. Wurzel), finden Sie das dort sitzende Element. b) Gegeben ein Element, finden Sie seinen Heap-Standort.

Das zweite ist sehr einfach: Fügen Sie einen Wert "Standort" hinzu (höchstwahrscheinlich einen Index in einem Array-basierten Heap), der jedes Mal aktualisiert wird, wenn das Element im Heap verschoben wird.

Das erste ist auch einfach: Anstatt Elemente zu speichern, behalten Sie einfach einen Heap von Zeigern auf Elemente (oder Array-Indizes) bei. Nun können Sie, gegeben ein Standort (z. B. Wurzel), das dort sitzende Element finden, indem Sie es dereferenzieren (oder auf den Vektor zugreifen).

Answer 5

Aber DELETE und DECREASE-KEY scheinen beide zu erfordern, dass die Prioritätswarteschlange in der Lage ist, den Index eines Elements im Heap zu finden, indem es das Element selbst übergeben wird.

Eigentlich ist das nicht wahr. Diese Operationen können in einem unindizierten Graphen, Verkettungen und "traditionellen" Suchbäumen implementiert werden, indem Vorgänger- und Nachfolgerzeiger vorhanden sind.