Positionsindex für binäre Heap-Prioritätswarteschlangen?

Question

Also sagen wir, ich habe eine Prioritätswarteschlange von N Elementen mit Prioritäten, wobei N in den Tausenden ist, unter Verwendung einer Prioritätswarteschlange, die mit einer binary heap implementiert ist. Ich verstehe die EXTRACT-MIN und INSERT Grundelemente (siehe Cormen, Leiserson, Rivest die -MAX statt -MIN verwendet).

Aber DELETE und DECREASE-KEY scheinen beide die Prioritätswarteschlange zu benötigen, um den Index eines Artikels in dem Heap zu finden, der das Element selbst gibt (alternativ muss dieser Index von Verbrauchern der Prioritätswarteschlange gegeben werden, aber dies scheint so eine Abstraktionsverletzung) .... die wie ein Versehen aussieht. Gibt es eine Möglichkeit, dies effizient zu tun, ohne eine Hashtabelle oben auf dem Heap hinzufügen zu müssen?

Answer 1

"Aber DELETE und DECREASE-KEY scheinen beide zu erfordern, dass die Prioritätswarteschlange den Index eines Artikels im Heap finden kann, wenn das Element selbst vorhanden ist" - das geht aus dem Code hervor, den zumindest einige dieser Methoden verwenden ein Index in den Heap und nicht die Priorität des Elements. Klar, ich bin ein Index in HEAP-INCREASE-KEY:

HEAP-INCREASE-KEY(A, i, key) 
    if key < A[i] 
     then error 'new key is smaller than current key" 
    A[i] <-- key 
    ... 

Also wenn das die API ist, benutze es.

Answer 2

Richtig, ich denke der Punkt hier ist, dass für die Implementierung der Prioritätswarteschlange Sie einen binären Heap verwenden können, dessen API einen Index (i) für seinen HEAP-INCREASE-KEY (A, i, Schlüssel), aber die Schnittstelle zur Prioritätswarteschlange kann einen beliebigen Schlüssel annehmen. Die Prioritätswarteschlange kann die Details von Schlüssel-> Index-Maps einkapseln. Wenn Sie Ihren PQ-INCREASE-KEY (A, alt, neu) benötigen, um in O zu arbeiten (log n), dann sollten Sie besser einen O (log n) oder besseren Schlüssel zum Index-Lookup haben, den Sie auf dem neuesten Stand halten. Das könnte eine Hash-Tabelle oder eine andere schnelle Suchstruktur sein.

Also, um Ihre Frage zu beantworten: Ich denke, es ist unvermeidlich, dass die Datenstruktur einige wie erweitert werden.

Answer 3

Ich habe meine Knotenklasse geändert, um ein heapIndex-Member hinzuzufügen. Dies wird durch den Heap beibehalten, da die Knoten beim Einfügen, Löschen, Verringern usw. getauscht werden.

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

Answer 4

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

Für die volle Funktionalität benötigen Sie zwei Beziehungen: a) Gegeben eine Heap Location (z. B. Root), finden Sie das Element dort sitzen. b) Gegeben sei ein Element, finde seine Heap Location.

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

Die erste ist auch einfach: Anstatt Elemente zu speichern, behalten Sie einfach einen Haufen Zeiger auf Elemente (oder Array-Indices). Bei einem Standort (z. B. Root) können Sie das Element dort finden, indem Sie es deneferenzieren (oder auf den Vektor zugreifen).

Answer 5

Aber DELETE und DECREASE-KEY scheinen sowohl die Prioritätswarteschlange erfordern eines Elements Index in der Halde das Element selbst Eigentlich

gegeben in der Lage sein zu finden, das ist nicht wahr. Sie können diese Operationen in einem nicht indizierten Graphen, Linked-Listen und 'traditionellen' Suchbäumen implementieren, indem Sie Vorgänger- und Nachfolgerzeiger haben.

Answer 6

FWIW, und wenn jemand immer noch auf der Suche nach etwas Ähnlichem kommt - ich bin kürzlich auf eine Implementierung für eine Indexed Prioritätswarteschlange gestoßen, während ich einen der Coursera Kurse über Algorithmen gemacht habe.

Der grundlegende Kern besteht darin, eine Reverse-Suche mit 2 Arrays zu integrieren, um die vom OP angegebenen Operationen zu unterstützen.

Hier ist eine klare Implementierung für Min Ordered Indexed Priority Queue.