Aufrechterhaltung invariant in Prim-Algorithmus

Question

Tim Roughgarden in Algorithmen 2 Kurs vermittelt den folgenden Ansatz für die benachbarten Knoten in dem min-Heap zu aktualisieren (nachdem er aus dem Heap Extrahieren min):

When a vertice v is added to the MST: 
    For each edge (v,w) in the unexplored tree: 
     1. Delete w from the min heap. 
     2. Recompute the key[w] (i.e. it's value from the unexplored tree 
     to the explored one). 
     3. Add the value back to the heap. 

Also, im Grunde handelt es sich dabei Streichung von der Haufen (und heapify, die nimmt O (log n))

statt und dann wieder einsetzen (wieder O (log n)), wenn ich den folgenden Ansatz:

For each edge (v,w) in the unexplored tree: 
    1. Get the position of the node in the heap(array) using HashMap -> O(1) 
    2. Update the value in place. 
    3. Bubble up or bubble down accordingly. -> O(logn) 

Althou Sie sind asymptotisch gleich, letzterer gibt bessere Konstanten. Also ist es besser als der im Kurs? Oder fehlt mir etwas?

Answer 1

Es ist asymptotisch das gleiche, und Sie würden mit einer hohen Wahrscheinlichkeit einen besseren konstanten Faktor erhalten. Was Sie mit HashMap erreichen möchten, verwendet O (n) zusätzlichen Speicherplatz. Auch in worst case, dauert es O (logn) zusätzliche Zeit, die gleiche wie eine Entfernung von Heap kosten würde. Allerdings ist seine Wahrscheinlichkeit der Zeit proportional zu logn ist sehr gering. Sie können in eine probabilistic performance analysis einer bestimmten HashMap-Implementierung schauen, die Sie verwenden möchten. wenn du daran interessiert bist, mehr darüber herauszufinden.

Ich könnte eine bessere Lösung vorschlagen, die die Verwendung von HashMap vermeidet, und ist folglich leichter zu beobachten/analysieren konstanten Faktor, da keine probabilistische Analyse erforderlich ist.

Die Lösung wird zum Speichern der Schlüsselwerte in einem externen Feld A und das Überschreiben der Vergleichsfunktion des Haufens so, dass sie die Elemente im Innern basierend auf ihren entsprechenden Werten vergleichen, die

Anders ausgedrückt in A gespeichert sind Die Standardvergleichsfunktion in vielen Heap-Implementierungen ist wie folgt.

function compare(a, b): 
    return a < b 

Während es aktualisiert wird, wird man es ändern:

function compare(a, b): 
    return A[a] < A[b] 

In Feld A, jeder Eckpunkt v wird eine entsprechende Zelle hat, wodurch O (n) zusätzliche Platznutzung, wie Ihre HashMap-Idee. Aber das Aktualisieren dieses Werts beim Hinzufügen von v zu den erkannten Knoten dauert auch im schlimmsten Fall.

Es ist möglicherweise nicht möglich, dieses Update basierend auf der Programmiersprache, in der Sie implementieren und Bibliotheken, die Sie für Heap verwenden, aber es ist möglich in vielen Sprachen und Sprachen einschließlich und nicht beschränkt auf C + + std :: priority_queue von STL. Sie können dies auch mit einer benutzerdefinierten Implementierung von Heap implementieren, wenn Sie mit einer solchen benutzerdefinierten Datenstruktur experimentieren möchten.