Warum heißt es in einer Warteschlange mit Mindestpriorität (Heap-basiert) "Verkleinerungsschlüssel" und nicht nur "Set-Schlüssel"?

Wenn Sie in einer Warteschlange mit Mindestpriorität den Verkleinerungsschlüssel aufrufen, legen Sie im Grunde den Schlüssel fest. Sie können versehentlich einen höheren Schlüssel eingeben, oder? Warum heißt es nicht "Set-Key" oder "Update-Key"? Warum (laut Wikipedia und anderen Quellen) hat eine Warteschlange mit minimaler Priorität "Schlüssel verringern" und eine Warteschlange mit maximaler Priorität "Schlüssel erhöhen"? Warum nicht beide "Set-Key" haben und wenn Sie ihn verringern oder erhöhen, tun Sie, was Sie tun sollten, um die Heap-Eigenschaft unveränderlich zu halten?

Ich meine, was ist, wenn ich auf einem Min-Heap die Abnahme-Taste aufrufe und einen größeren Wert gebe? Wird es eine Ausnahme werfen? Warum nennst du es nicht einfach "Set-Key" und handhabst jede Art von Wert?

Gute Frage. Eine der wichtigsten Anwendungen der Datenstruktur PriorityQueue ist der Dijkstra-Algorithmus. Jeder Knoten erhält eine Entfernung vom Anfangsknoten, die aktualisiert wird, wenn kürzere Pfade erkannt werden. Daher ändern Aktualisierungen nur den Schlüssel in eine Richtung.

Das Problem bei der Implementierung von DecreaseKey ist nicht, dass es nur abnimmt (anstatt den Wert zu aktualisieren). Für einen binären Heap gibt es sehr effiziente Methoden zum Erhöhen und Verringern. Beide tauschen Knoten mit anderen Knoten entlang eines Pfades im Baum aus (entweder nach oben oder nach unten). Das Problem ist tatsächlich zu wissen, wo der Schlüssel zu finden ist. Sie können nicht effizient danach suchen, daher muss ein separater "Index" geführt werden. Wenn eine Aktualisierung entlang eines Pfads durchgeführt wird, wird nicht nur der verkleinerte Schlüssel im Indax geändert, sondern auch die anderen Schlüssel entlang des Pfads.

Für abstrakte Datenstrukturen möchten wir nur die Operationen angeben , die in einem bestimmten Kontext wichtig sind. Angesichts der Dijkstra-Motivation haben wir also nur DecreaseKey. Obwohl das Erweitern der Operationen für binäre Heaps elementar sein kann, ist dies bei anderen Implementierungen der PriorityQueue wie Leftist Heaps, Fibonacci Heaps oder Brodal Heaps möglicherweise nicht der Fall.

Was eine bestimmte Implementierung tun wird, wenn der neue Wert in die falsche Richtung weist, hängt von dieser Implementierung ab.

Die Benennung der Methode ist in einigen Lehrbüchern (z. B. CLRS ) wahrscheinlich absichtlich, weil:

1. Die Logik zum "Schweben" oder "Sprudeln" eines Schlüssels in einem binären Heap ist unkompliziert, wenn Sie wissen, in welche Richtung (nach oben / unten) Sie gehen. Zum Beispiel ist das "Sprudeln" eines Schlüssels einfach ein rekursiver Aufruf der Knoteneltern, anstatt nach unten zu schweben, wo Sie mit jedem Kind vergleichen müssen , bevor Sie rekursiv fortfahren.
2. Bei vielen Algorithmen, die Max / Min-Heaps verwenden, müssen Sie nur die Tasten erhöhen oder verringern. Daher reicht es aus, die entsprechende Methode "Floating Down" oder "Bubbling Up" bereitzustellen.

Beachten Sie, dass Sie, wenn Sie eine generische "Set Key" -Methode implementieren möchten, diese beiden Routinen einfach kombinieren können, um zu entscheiden, in welche Richtung Sie gehen möchten, je nachdem, ob Sie den Schlüssel sprudeln oder nach unten schweben müssen.

Um das zu ergänzen, was Hendrick gesagt hat, ist es erwähnenswert, dass selbst für die Algorithmen von Dijkstra oder Prim, bei denen technisch gesehen eine Operation zum Verringern der Schlüssel ausreicht, die Verwendung eines binären Heaps nicht unbedingt erfordert, dass Sie die Position jedes Schlüssels verfolgen.

Bei diesen Algorithmen wird ein bestimmter Schlüssel nur einmal aus dem Heap extrahiert . Zum Beispiel in Dijkstra ist ein Graph Knoten nur einmal hinzugefügt , um den kürzesten Pfade Baum, und im Prim-Algorithmus, eine Kante kann nur einmal auf den minimalen Spanning - Tree hinzugefügt werden.

Anstatt die Schlüsselpositionen zu verfolgen (oder nach ihnen zu suchen, wenn der Algorithmus sie verringern muss), kann on einfach den neuen (in diesem Fall niedrigeren ) Wert für den Schlüssel in den Heap einfügen (was zu Duplikaten im Heap führt). Sobald Sie den "Schlüssel" aus dem Heap extrahiert haben (technisch gesehen Satellitendaten, da der Schlüssel nicht das ist, was Sie gierig verbrauchen), können Sie alle nachfolgenden Extraktionen ignorieren (z. B. mithilfe eines Sets mit$O(1)$).

Solche Set- und Key-Duplikate im Heap würden Sie offensichtlich kosten $O(n)$in der Raumkomplexität, aber Sie könnten sich die kombinierte Lösung als eine "Schlüssel verringern" -Methode vorstellen, die keine Kenntnis oder Verfolgung von Positionen im Heap erfordert .