Warum hat die Warteschlange mit der maximalen Priorität nicht DECREASE-KEY?

Question

Warum hat die Warteschlange mit der maximalen Priorität nicht DECREASE-KEY?

8

Bei der Erörterung der Heap-Datenstruktur, beispielsweise in CLRS , benötigt die Warteschlange für die maximale Priorität nur INSERT, MAXIMUM , EXTRACT-MAX und INCREASE-KEY. Aber warum hat es nicht auch DECREASE-KEY, dessen Operation wird auch die Heap-Eigenschaft ungültig machen? Ist es praktisch unwichtig?

algorithm data-structures

Qiang Li 09.11.2011, 19:43

quelle

3 Antworten

Tags und Links algorithm data-structures

Django: Verwenden von Annotate, Count und Distinct in einem Queryset android webview tastatur erscheint nicht lange für die Eingabe von Werten

score 3 · Answer 1

3

Nichts hält Sie davon ab, DECREASE-KEY in Ihrem binären Heap zu implementieren. Es kann in O (log N) gemacht werden, ohne Invarianten zu brechen.

Meine Vermutung ist, dass es nicht enthalten ist, weil es nicht sehr oft benötigt wird.

svick 09.11.2011 23:12

quelle

score 1 · Answer 2

FWIW Meine CLR V1 spricht von INSERT, MIN, EXTRACT-MIN, UNION, DECREASE-KEY und DELETE, aber wir können sie in Ihre Version umwandeln, indem wir Zeichen umdrehen.

Ich denke, diese Menge wird von den Anforderungen der Algorithmen bestimmt, die Prioritätswarteschlangen verwenden, wie zum Beispiel den minimalen Spannbaum, Dijstras kürzesten Pfad und (ich vermute,) A *. Wenn Sie beispielsweise den Anfang des Kapitels über minimale Spannbäume betrachten, können Sie eine Notiz sehen, dass der Algorithmus von Prim beschleunigt werden kann, wenn Sie binäre Haufen durch Fibonacci-Haufen ersetzen.

score 1 · Answer 3

1

Wenn Sie ein MAX-HEAP haben, wird DECREASE-KEY MAX-HEAPIFY in Abschnitt 6.2 "Verwalten der Heap-Eigenschaft" von CLRS, 3. Ausgabe.

chill 10.11.2011 13:31

quelle