Implementieren der Prioritätswarteschlange mit maximalem Heap im Vergleich zu ausgeglichenem BST
Balanced BST und Max Heap führen sowohl das Einfügen als auch das Löschen durch O(logn). Das Finden des Maximalwerts in einem Maximalhaufen erfolgt O(1)jedoch O(logn)in ausgeglichener BST.
Wenn wir den Maximalwert in einem Maximalheap entfernen, wird dies benötigt, O(logn)da es sich um eine Löschoperation handelt.
In ausgeglichener BST wird das max-Element gelöscht = maximaler Wert gefunden + gelöscht; es ist gleich logn + logn reduziert sich auf O(logn). So ist auch das Löschen des Maximalwertes in ausgeglichener BST O(logn).
Ich habe gelesen, dass eine solche Anwendung von max heap eine Prioritätswarteschlange ist und ihr Hauptzweck darin besteht, den maximalen Wert für jede Dequeue-Operation zu entfernen. Wenn das Löschen des max-Elements O(logn)sowohl für den maximalen Heap als auch für die ausgeglichene BST gilt, habe ich die folgenden Fragen
Was ist der Zweck eines maximalen Heaps in der Prioritätswarteschlange, nur weil er einfach zu implementieren ist, anstatt eine vollständig durchsuchbare ausgeglichene BST zu verwenden?
Da es keine Ausgleichsfaktorberechnung gibt, kann der maximale Heap als unausgeglichener Binärbaum bezeichnet werden.
Jede ausgeglichene BST kann als Prioritätswarteschlange verwendet werden und welche kann auch durchsucht werden, wenn
O(logn)jedoch die maximale Heap-SucheO(n)korrekt ist?
Alle Zeitkomplexitäten werden für den schlimmsten Fall berechnet. Jede Hilfe wird sehr geschätzt.
Antworten
Was ist der Zweck eines maximalen Heaps in der Prioritätswarteschlange, nur weil er einfach zu implementieren ist, anstatt eine vollständig durchsuchbare ausgeglichene BST zu verwenden?
Einige Vorteile eines Haufens sind:
Gegeben eine unsortierte Eingangsanordnung, einer kann heap noch eingebaut werden O (n) Zeit , während ein BST benötigt O (n log n) Zeit .
Wenn die anfängliche Eingabe ein Array ist, kann dasselbe Array als Heap dienen, was bedeutet, dass kein zusätzlicher Speicher dafür benötigt wird. Obwohl man sich Möglichkeiten vorstellen könnte, eine BST unter Verwendung der im Array vorhandenen Daten zu erstellen, wäre dies ziemlich seltsam (für primitive Typen) und würde mehr Verarbeitungsaufwand verursachen. Ein BST wird normalerweise von Grund auf neu erstellt und kopiert die Daten beim Erstellen in die Knoten.
Interessante Tatsache: Ein sortiertes Array ist auch ein Heap. Wenn also bekannt ist, dass die Eingabe sortiert ist, muss nichts unternommen werden, um den Heap zu erstellen.
Ein Heap kann als Array gespeichert werden, ohne dass Querverweise gespeichert werden müssen , während ein BST normalerweise aus Knoten mit Links- und Rechtsreferenzen besteht. Dies hat mindestens zwei Konsequenzen:
- Der für eine BST verwendete Speicher ist ungefähr dreimal so groß wie für einen Heap.
- Obwohl mehrere Operationen sowohl für Heap als auch für BST die gleiche Zeitkomplexität haben, ist der Aufwand für die Anpassung einer BST viel größer, so dass die tatsächliche Zeit, die für diese Operationen aufgewendet wird, im BST-Fall ein (konstanter) Faktor ist.
Da es keine Ausgleichsfaktorberechnung gibt, kann der maximale Heap als unausgeglichener Binärbaum bezeichnet werden.
Ein Haufen ist in der Tat ein vollständiger Binärbaum , daher ist er immer so ausgewogen wie möglich: Die Blätter werden immer in der letzten oder vorletzten Ebene positioniert. Eine selbstausgleichende BST (wie AVL, rot-schwarz, ...) kann dieses hohe Ausgleichsniveau nicht übertreffen, bei dem häufig Blätter auf drei oder mehr Ebenen auftreten.
Jede ausgeglichene BST kann als Prioritätswarteschlange verwendet werden und welche kann auch in O (logn) durchsucht werden. Ist die maximale Heap-Suche jedoch O (n) korrekt?
Ja, das stimmt. Wenn die Anwendung die Suchfunktion benötigt, ist eine BST überlegen.
Was ist der Zweck eines maximalen Heaps in der Prioritätswarteschlange, nur weil er einfach zu implementieren ist, anstatt eine vollständig durchsuchbare ausgeglichene BST zu verwenden?
Nee. Der maximale Heap passt besser, da er sorgfältig instrumentiert ist, um das nächste Element (unter Berücksichtigung der Priorität) so schnell wie möglich in O (1) -Zeit zurückzugeben. Das ist es, was Sie von der einfachsten Prioritätswarteschlange erwarten.
Da es keine Ausgleichsfaktorberechnung gibt, kann der maximale Heap als unausgeglichener Binärbaum bezeichnet werden.
Nee. Es gibt auch ein Gleichgewicht. Kurz gesagt, das Ausbalancieren eines Haufens erfolgt durch Hoch- oder Herunterschalten (Austauschen von Elementen, die nicht in Ordnung sind).
Jede ausgeglichene BST kann als Prioritätswarteschlange verwendet werden und welche kann auch in O (logn) durchsucht werden. Ist die maximale Heap-Suche jedoch O (n) korrekt?
Ja! Ebenso könnte eine verknüpfte Liste oder ein Array verwendet werden. Es wird nur teurer in Bezug auf die O-Notation und viel langsamer in der Praxis.