Heap vs Binary Search Tree (BST)

169

Was ist der Unterschied zwischen einem Haufen und BST?

Wann sollte ein Heap und wann ein BST verwendet werden?

Wenn Sie die Elemente sortiert erhalten möchten, ist BST besser als Heap?

kc3
quelle
13
Diese Frage scheint nicht zum Thema zu gehören, da es sich um Informatik handelt und auf cs.stackexchange.com
Flow
3
@Flow wurde dort gefragt: cs.stackexchange.com/questions/27860/…
Ciro Santilli 9 冠状 病 六四 六四 法轮功
3
Ich denke, es bezieht sich sowohl auf den Stapelaustausch als auch auf den Stapelüberlauf. Es ist also in Ordnung, es hier zu haben
Azizbro

Antworten:

190

Zusammenfassung

          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

Alle Durchschnittszeiten in dieser Tabelle entsprechen den schlechtesten Zeiten mit Ausnahme von Einfügen.

  • *: überall in dieser Antwort, BST == Balanced BST, da Unbalanced asymptotisch saugt
  • **: Verwenden einer trivialen Modifikation, die in dieser Antwort erläutert wird
  • ***: log(n)für Zeigerbaum-Heap, nfür dynamischen Array-Heap

Vorteile eines binären Heaps gegenüber einer BST

  • Die durchschnittliche Zeiteinfügung in einen binären Heap beträgt O(1)für BST O(log(n)). Dies ist das Killer-Feature von Haufen.

    Es gibt auch andere Haufen, die O(1)amortisiert (stärker) sind, wie der Fibonacci-Haufen , und sogar den schlimmsten Fall, wie die Brodal-Warteschlange , obwohl sie aufgrund der nicht asymptotischen Leistung möglicherweise nicht praktikabel sind: Werden Fibonacci-Haufen oder Brodal-Warteschlangen in der Praxis irgendwo verwendet?

  • Binäre Heaps können effizient über dynamische Arrays oder zeigerbasierte Bäume implementiert werden , BST nur zeigerbasierte Bäume. Für den Heap können wir also die platzsparendere Array-Implementierung wählen, wenn wir uns gelegentliche Latenzzeiten für die Größenänderung leisten können.

  • binäre Heap Schöpfung ist O(n)schlimmster Fall , O(n log(n))für BST.

Vorteil von BST gegenüber binärem Heap

  • Suche nach beliebigen Elementen ist O(log(n)). Dies ist das Killer-Feature von BSTs.

    Für Heap ist es O(n)im Allgemeinen, mit Ausnahme des größten Elements, das ist O(1).

"Falscher" Vorteil von Heap gegenüber BST

  • Haufen ist O(1)max, BST zu finden O(log(n)).

    Dies ist ein weit verbreitetes Missverständnis, da es trivial ist, eine BST zu ändern, um das größte Element im Auge zu behalten, und es zu aktualisieren, wann immer dieses Element geändert werden könnte: Beim Einfügen eines größeren Swaps finden Sie beim Entfernen das zweitgrößte. Können wir einen binären Suchbaum verwenden, um die Heap-Operation zu simulieren? ( von Yeo erwähnt ).

    Tatsächlich ist dies eine Einschränkung von Heaps im Vergleich zu BSTs: Die einzige effiziente Suche ist die nach dem größten Element.

Die durchschnittliche binäre Heap-Einfügung beträgt O(1)

Quellen:

Intuitives Argument:

  • Die unteren Baumebenen haben exponentiell mehr Elemente als die oberen Ebenen, sodass neue Elemente mit ziemlicher Sicherheit am unteren Rand angezeigt werden
  • Das Einfügen von Heaps beginnt von unten , BST muss von oben beginnen

In einem binären Heap hat das Erhöhen des Werts bei einem bestimmten Index ebenfalls O(1)den gleichen Grund. Wenn Sie dies tun möchten, ist es wahrscheinlich, dass Sie einen zusätzlichen Index für Heap-Vorgänge auf dem neuesten Stand halten möchten . zB für Dijkstra. Ohne zusätzliche Zeitkosten möglich.

Benchmark zum Einfügen von GCC C ++ - Standardbibliotheken auf echte Hardware

Ich habe das C ++ std::set( Red-Black Tree BST ) und das std::priority_queue( Dynamic Array Heap ) Insert verglichen, um festzustellen, ob ich mit den Einfügezeiten Recht hatte, und Folgendes habe ich erhalten:

Geben Sie hier die Bildbeschreibung ein

  • Benchmark-Code
  • Handlungsskript
  • Plotdaten
  • Getestet unter Ubuntu 19.04, GCC 8.3.0 in einem Lenovo ThinkPad P51-Laptop mit CPU: Intel Core i7-7820HQ-CPU (4 Kerne / 8 Threads, 2,90 GHz-Basis, 8 MB Cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16 GB) , 2400 Mbit / s), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3.000 MB / s)

So klar:

  • Die Heap-Einfügungszeit ist grundsätzlich konstant.

    Wir können deutlich sehen, wie dynamische Array-Größenpunkte geändert werden. Da wir alle 10.000 Einfügungen mitteln , um überhaupt etwas über dem Systemrauschen zu sehen , sind diese Spitzen tatsächlich etwa 10.000 Mal größer als gezeigt!

    Das gezoomte Diagramm schließt im Wesentlichen nur die Größenänderungspunkte des Arrays aus und zeigt, dass fast alle Inserts unter 25 Nanosekunden fallen.

  • BST ist logarithmisch. Alle Einfügungen sind viel langsamer als die durchschnittliche Heap-Einfügung.

  • BST vs hashmap detaillierte Analyse unter: Welche Datenstruktur befindet sich in std :: map in C ++?

Benchmark zum Einfügen von GCC C ++ - Standardbibliotheken auf gem5

gem5 ist ein Vollsystem- Simulator und liefert daher eine unendlich genaue Uhr mit m5 dumpstats. Also habe ich versucht, damit die Timings für einzelne Beilagen zu schätzen.

Geben Sie hier die Bildbeschreibung ein

Deutung:

  • Heap ist immer noch konstant, aber jetzt sehen wir genauer, dass es einige Zeilen gibt und jede höhere Zeile spärlicher ist.

    Dies muss den Speicherzugriffslatenzen entsprechen, die für immer höhere Einfügungen durchgeführt werden.

  • TODO Ich kann das BST nicht wirklich vollständig interpretieren, da es nicht so logarithmisch und etwas konstanter aussieht.

    Mit diesem größeren Detail können wir jedoch auch einige unterschiedliche Linien sehen, aber ich bin nicht sicher, was sie darstellen: Ich würde erwarten, dass die untere Linie dünner ist, da wir oben unten einfügen?

Benchmarking mit diesem Buildroot-Setup auf einer aarch64 HPI-CPU .

BST kann nicht effizient auf einem Array implementiert werden

Heap-Operationen müssen nur einen einzelnen Ast hoch oder runter sprudeln, so dass O(log(n))Swaps im schlimmsten Fall O(1)durchschnittlich sind.

Um eine BST im Gleichgewicht zu halten, sind Baumrotationen erforderlich, bei denen das obere Element durch ein anderes ersetzt werden kann, und das gesamte Array muss verschoben werden ( O(n)).

Heaps können effizient auf einem Array implementiert werden

Übergeordnete und untergeordnete Indizes können wie hier gezeigt aus dem aktuellen Index berechnet werden .

Es gibt keine Ausgleichsvorgänge wie BST.

Min. Löschen ist der besorgniserregendste Vorgang, da es von oben nach unten erfolgen muss. Dies kann jedoch immer durch "Versickern" eines einzelnen Zweigs des Haufens erfolgen, wie hier erläutert . Dies führt zu einem O (log (n)) - Worst-Case, da der Heap immer gut ausbalanciert ist.

Wenn Sie für jeden entfernten Knoten einen einzelnen Knoten einfügen, verlieren Sie den Vorteil des asymptotischen O (1) -Durchschnitts, den Heaps bieten, da das Löschen dominieren würde, und Sie können auch eine BST verwenden. Dijkstra aktualisiert die Knoten jedoch mehrmals für jede Entfernung, sodass es uns gut geht.

Dynamische Array-Heaps gegen Zeigerbaum-Heaps

Heaps können effizient über Zeiger-Heaps implementiert werden: Ist es möglich, effiziente zeigerbasierte binäre Heap-Implementierungen durchzuführen?

Die Implementierung eines dynamischen Arrays ist platzsparender. Angenommen, jedes Heap-Element enthält nur einen Zeiger auf a struct:

  • Die Baumimplementierung muss drei Zeiger für jedes Element speichern: Eltern, linkes Kind und rechtes Kind. Die Speichernutzung beträgt also immer 4n(3 Baumzeiger + 1 structZeiger).

    Baum-BSTs würden auch weitere Ausgleichsinformationen benötigen, z. B. Schwarz-Rot.

  • Die Implementierung des dynamischen Arrays kann 2nunmittelbar nach einer Verdoppelung von der Größe sein . So wird es im Durchschnitt sein 1.5n.

Auf der anderen Seite hat der Baumheap eine bessere Einfügung im ungünstigsten Fall, da das Kopieren des dynamischen Backing-Arrays auf die doppelte Größe im O(n)ungünstigsten Fall erfolgt, während der Baumheap nur neue kleine Zuweisungen für jeden Knoten ausführt.

Die Verdoppelung des Backing-Arrays wird jedoch O(1)amortisiert, sodass eine maximale Latenz berücksichtigt wird. Hier erwähnt .

Philosophie

  • BSTs behalten eine globale Eigenschaft zwischen einem Elternteil und allen Nachkommen bei (links kleiner, rechts größer).

    Der oberste Knoten einer BST ist das mittlere Element, für dessen Aufrechterhaltung globales Wissen erforderlich ist (Wissen, wie viele kleinere und größere Elemente vorhanden sind).

    Die Wartung dieser globalen Eigenschaft ist teurer (log n insert), bietet jedoch leistungsfähigere Suchvorgänge (log n search).

  • Heaps verwalten eine lokale Eigenschaft zwischen übergeordneten und direkten Kindern (Eltern> Kinder).

    Der oberste Knoten eines Heaps ist das große Element, für dessen Pflege nur lokales Wissen erforderlich ist (Kenntnis Ihres Elternteils).

Vergleich von BST vs Heap vs Hashmap:

  • BST: kann entweder eine vernünftige sein:

    • ungeordnete Menge (eine Struktur, die bestimmt, ob ein Element zuvor eingefügt wurde oder nicht). Die Hashmap ist jedoch aufgrund des amortisierten O (1) -Einsatzes tendenziell besser.
    • Sortiermaschine. Aber Heap ist im Allgemeinen besser darin, weshalb Heapsort viel bekannter ist als Baumsortierung
  • Haufen: ist nur eine Sortiermaschine. Kann keine effiziente ungeordnete Menge sein, da Sie nur schnell nach dem kleinsten / größten Element suchen können.

  • Hash-Map: Kann nur ein ungeordneter Satz sein, keine effiziente Sortiermaschine, da der Hashing jede Reihenfolge verwechselt.

Doppelt verknüpfte Liste

Eine doppelt verknüpfte Liste kann als Teilmenge des Heaps angesehen werden, in dem das erste Element die höchste Priorität hat. Vergleichen wir sie also auch hier:

  • Einfügung:
    • Position:
      • doppelt verknüpfte Liste: Das eingefügte Element muss entweder das erste oder das letzte sein, da wir nur Zeiger auf diese Elemente haben.
      • Binärer Heap: Das eingefügte Element kann an einer beliebigen Position landen. Weniger restriktiv als verknüpfte Liste.
    • Zeit:
      • doppelt verknüpfte Liste: O(1)Worst-Case, da wir Zeiger auf die Elemente haben und das Update wirklich einfach ist
      • Binärheap: O(1)Durchschnitt, also schlechter als verknüpfte Liste. Kompromiss für eine allgemeinere Einfügeposition.
  • Suche: O(n)für beide

Ein Anwendungsfall hierfür ist, wenn der Schlüssel des Heaps der aktuelle Zeitstempel ist: In diesem Fall werden neue Einträge immer an den Anfang der Liste gesetzt. So können wir sogar den genauen Zeitstempel ganz vergessen und einfach die Position in der Liste als Priorität behalten.

Dies kann verwendet werden, um einen LRU-Cache zu implementieren . Genau wie bei Heap-Anwendungen wie Dijkstra möchten Sie eine zusätzliche Hashmap vom Schlüssel zum entsprechenden Knoten der Liste behalten, um herauszufinden, welcher Knoten schnell aktualisiert werden soll.

Vergleich verschiedener ausgeglichener BST

Obwohl die asymptotischen Einfüge- und Suchzeiten für alle Datenstrukturen, die üblicherweise als "ausgeglichene BSTs" klassifiziert werden, die ich bisher gesehen habe, gleich sind, haben verschiedene BBSTs unterschiedliche Kompromisse. Ich habe dies noch nicht vollständig studiert, aber es wäre gut, diese Kompromisse hier zusammenzufassen:

  • Rot-schwarzer Baum . Scheint ab 2019 das am häufigsten verwendete BBST zu sein, z. B. das von der GCC 8.3.0 C ++ - Implementierung verwendete
  • AVL-Baum . Scheint etwas ausgeglichener zu sein als BST, daher könnte es besser sein, die Latenz auf Kosten etwas teurerer Funde zu finden. Das Wiki fasst zusammen: "AVL-Bäume werden häufig mit rot-schwarzen Bäumen verglichen, da beide die gleichen Operationen unterstützen und für die grundlegenden Operationen [die gleiche] Zeit benötigen. Für Anwendungen mit hoher Suchintensität sind AVL-Bäume schneller als rot-schwarze Bäume, weil Sie sind strenger ausbalanciert. Ähnlich wie rot-schwarze Bäume sind AVL-Bäume höhenausgeglichen. Beide sind im Allgemeinen weder gewichtsausgeglichen noch mu-ausgeglichen für jedes mu <1/2, dh Geschwisterknoten können enorm sein unterschiedliche Anzahl von Nachkommen. "
  • WAVL . Das Originalpapier erwähnt die Vorteile dieser Version in Bezug auf die Grenzen der Neuausgleichs- und Rotationsoperationen.

Siehe auch

Ähnliche Frage zu CS: /cs/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
quelle
4
I + 1ed, aber das "Papier", das die durchschnittliche Einfügung von O (1) -Binärhaufen rechtfertigt, ist jetzt ein toter Link, und die "Folien" geben nur die Behauptung ohne Beweis an. Ich denke auch, dass es hilfreich wäre zu klären, dass "durchschnittlicher Fall" hier den Durchschnitt bedeutet, vorausgesetzt, dass eingefügte Werte aus einer bestimmten Verteilung stammen , daher bin ich mir nicht sicher, wie "Killer" diese Funktion wirklich ist.
j_random_hacker
3
BST und Balanced BST scheinen austauschbar zu sein. Es sollte klargestellt werden, dass sich die Antwort auf eine ausgewogene BST bezieht, um Verwirrung zu vermeiden.
gkalpak
2
@Bulat Ich glaube, wir schweifen ein wenig ab, aber wenn wir gleichzeitig Max und Min wollen, können Probleme mit der Wartung von zwei Heaps auftreten, wenn wir nicht vorsichtig sind - stackoverflow.com/a/1098454/7154924 . Es ist wahrscheinlich besser, einen Max-Min-Haufen zu verwenden (aufgrund von Atkinson et al.), Der speziell für diesen Zweck entwickelt wurde.
flow2k
1
@CiroSantilli I 改造 中心 六四 六四 法轮功: Ich verstehe nicht, warum der Löschvorgang eines binären Heaps O (log n) ist. Dies funktioniert nur, wenn Sie einen Zeiger auf das Element im Heap haben. In den meisten Anwendungsfällen haben Sie jedoch den Schlüssel und müssen zuerst das Element finden, das O (n) benötigt.
Ricola
5
Heap-Einfügung ist log (n) nicht o (1)
Bobo
78

Heap garantiert nur, dass Elemente auf höheren Ebenen größer (für Max-Heap) oder kleiner (für Min-Heap) sind als Elemente auf niedrigeren Ebenen, während BST die Reihenfolge garantiert (von "links" nach "rechts"). Wenn Sie sortierte Elemente wünschen, wählen Sie BST.

Dante May Code
quelle
8
"Heap garantiert nur, dass Elemente auf höheren Ebenen größer (für Max-Heap) oder kleiner (für Min-Heap) sind als Elemente auf niedrigeren Ebenen, ..." - der Heap erzwingt dies nicht pro Ebene , sondern nur in Eltern-Kind- Ketten. [1, 5, 9, 7, 15, 10, 11]stellt einen gültigen Min-Heap dar, aber der 7auf Ebene 3 ist kleiner als 9auf Ebene 2. Für eine Visualisierung siehe z. B. die 25und 19Elemente im Beispiel-Wikipedia-Bild für Heaps . (Beachten Sie auch, dass die Ungleichheitsbeziehungen zwischen Elementen nicht streng sind, da Elemente nicht unbedingt eindeutig sind.)
Daniel Andersson
Entschuldigung für den späten Einstieg, aber ich möchte nur Klarheit bekommen. Wenn der binäre Heap sortiert ist, ist der schlechteste Fall für die Suche log n richtig. In diesem Fall sind binäre Heaps besser sortiert als binäre Suchbäume (Rot-Schwarz-BST). Vielen Dank
Krishna
49

Wann ein Heap und wann ein BST verwendet werden soll

Heap ist besser bei findMin / FindMax ( O(1)), während BST gut ist alle (Funde O(logN)). Einfügen ist O(logN)für beide Strukturen. Wenn Sie sich nur für findMin / findMax interessieren (z. B. prioritätsbezogen), wählen Sie Heap. Wenn Sie alles sortieren möchten, wählen Sie BST.

Die ersten paar Folien von hier erklären die Dinge sehr klar.

xysun
quelle
3
Während das Einfügen im schlimmsten Fall für beide logarithmisch ist, benötigt das durchschnittliche Heap-Einfügen eine konstante Zeit. (Da sich die meisten vorhandenen Elemente unten befinden, muss ein neues Element in den meisten Fällen, wenn überhaupt, nur ein oder zwei Ebenen
hochsprudeln
1
@xysun Ich denke, BST ist besser in findMin & findMax stackoverflow.com/a/27074221/764592
Yeo
2
@Yeo: Heap ist besser für findMin xor findMax. Wenn Sie beide benötigen , ist BST besser.
Mooing Duck
1
Ich denke, das ist nur ein häufiges Missverständnis. Ein Binärbaum kann leicht modifiziert werden, um Min und Max zu finden, wie von Yeo angegeben. Dies ist eigentlich eine Einschränkung des Heaps: Der einzige effiziente Fund ist min oder max. Der wahre Vorteil des Haufens ist die durchschnittliche Einfügung von O (1), wie ich erkläre: stackoverflow.com/a/29548834/895245
Ciro Santilli 20 冠状. 六四 事件 20
1
Ciro Santillis Antwort ist weitaus besser: stackoverflow.com/a/29548834/2873507
Vic Seedoubleyew
9

Wie von anderen erwähnt, kann Heap findMin oder findMax in O (1), aber nicht beide in derselben Datenstruktur. Ich bin jedoch nicht der Meinung, dass Heap in findMin / findMax besser ist. Tatsächlich kann die BST mit einer geringfügigen Modifikation beides findMin und findMax in O (1) tun .

In dieser modifizierten BST verfolgen Sie den Min- und Max-Knoten jedes Mal, wenn Sie eine Operation ausführen, die möglicherweise die Datenstruktur ändern kann. Beispielsweise können Sie beim Einfügen überprüfen, ob der Mindestwert größer als der neu eingefügte Wert ist, und dann den Mindestwert dem neu hinzugefügten Knoten zuweisen. Die gleiche Technik kann auf den Maximalwert angewendet werden. Daher enthält diese BST diese Informationen, die Sie in O (1) abrufen können. (wie binärer Heap)

In dieser BST (Balanced BST) ist, wenn Sie pop minoder pop max, der nächste zuzuweisende Min-Wert der Nachfolger des Min-Knotens, während der nächste zuzuweisende Max-Wert der Vorgänger des Max-Knotens ist. Somit wird es in O (1) ausgeführt. Wir müssen den Baum jedoch neu ausbalancieren, damit er weiterhin O (log n) ausführt. (wie binärer Heap)

Es würde mich interessieren, Ihre Gedanken im Kommentar unten zu hören. Vielen Dank :)

Aktualisieren

Querverweis auf eine ähnliche Frage Können wir einen binären Suchbaum verwenden, um die Heap-Operation zu simulieren? Weitere Informationen zur Simulation von Heap mit BST.

Yeo
quelle
Warum bist du anderer Meinung? Würde es Ihnen etwas ausmachen, Ihre Gedanken weiter unten zu teilen?
Yeo
Sie könnten sicherlich den Maximal- und / oder Minimalwert einer BST speichern, aber was passiert dann, wenn Sie sie platzen lassen möchten? Sie müssen den Baum durchsuchen, um ihn zu entfernen, und dann erneut nach dem neuen Maximum / Min suchen. Beide sind O (log n) -Operationen. Dies entspricht der Reihenfolge des Einfügens und Entfernens in einem Prioritätshaufen mit einer schlechteren Konstante.
Justin
@ JustinLardinois Entschuldigung, ich habe vergessen, dies in meiner Antwort hervorzuheben. Wenn Sie in BST Pop-Min ausführen, ist der nächste zuzuweisende Min-Wert der Nachfolger des Min-Knotens. Wenn Sie das Maximum eingeben, ist der nächste zuzuweisende Maximalwert der Vorgänger des Max-Knotens. Somit arbeitet es immer noch in O (1).
Yeo
Korrektur: für popMinoder popMaxes ist nicht O (1), aber es ist O (log n), weil es eine ausgeglichene BST sein muss, die bei jedem Löschvorgang neu ausgeglichen werden muss. Daher ist es dasselbe wie ein binärer Heap popMinoder popMaxder O (log n)
ausführt
2
Sie können das erste min / max erhalten, aber das kth min / max würde zur normalen BST-Komplexität zurückkehren.
Chaos
3

Ein binärer Suchbaum verwendet die Definition: Für jeden Knoten hat der Knoten links davon einen geringeren Wert (Schlüssel) und der Knoten rechts davon einen größeren Wert (Schlüssel).

Als Heap wird für die Implementierung eines Binärbaums die folgende Definition verwendet:

Wenn A und B Knoten sind, wobei B der untergeordnete Knoten von A ist, muss der Wert (Schlüssel) von A größer oder gleich dem Wert (Schlüssel) von B sein. Das heißt, Schlüssel (A) ≥ Schlüssel (B. ).

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

Ich habe heute dieselbe Frage für meine Prüfung gestellt und es richtig verstanden. lächeln ... :)

Yevgraf Andreyevich Zhivago
quelle
"Heap, eine Implementierung des Binärbaums" - nur darauf hinweisen, dass ein Heap eine Art Binärbaum ist, keine Art von BST
Saad
3

Eine andere Verwendung von BST über Heap; wegen eines wichtigen Unterschieds:

  • Das Finden von Nachfolger und Vorgänger in einer BST dauert O (h) Zeit. (O (logn) in ausgeglichener BST)
  • würde in Heap O (n) Zeit brauchen, um Nachfolger oder Vorgänger eines Elements zu finden.

Verwendung von BST über einen Haufen : Nehmen wir nun an, wir verwenden eine Datenstruktur, um die Landezeit von Flügen zu speichern. Wir können keinen Flug zur Landung planen, wenn der Unterschied in den Landezeiten weniger als 'd' beträgt. Angenommen, viele Flüge sollen in einer Datenstruktur (BST oder Heap) landen.

Jetzt wollen wir einen weiteren Flug planen, der um t landet . Daher müssen wir die Differenz von t mit seinem Nachfolger und Vorgänger berechnen (sollte> d sein). Daher benötigen wir hierfür eine BST, die es schnell macht, dh in O (logn), wenn sie ausgeglichen ist.

BEARBEITET:

Das Sortieren von BST benötigt O (n) Zeit, um Elemente in sortierter Reihenfolge zu drucken (Inorder Traversal), während Heap dies in O (n logn) Zeit tun kann. Heap extrahiert das min-Element und Heapifiziert das Array erneut, wodurch die Sortierung in O (n logn) -Zeit erfolgt.

CODError
quelle
1
Ja. Es ist von unsortierter zu sortierter Reihenfolge. O (n) Zeit für das Durchlaufen einer BST in der Reihenfolge, was eine sortierte Sequenz ergibt. Während Sie sich in Heaps befinden, extrahieren Sie das min-Element und haufen es dann in O (log n) erneut ein. SO wird O (n logn) benötigt, um n Elemente zu extrahieren. Und Sie erhalten eine sortierte Reihenfolge.
CODError
from unsorted to sorted sequence. O(n) time for inorder traversal of a BST, which gives sorted sequence.Nun, von der unsortierten Sequenz bis zur BST kenne ich keine Methode, die auf einem Schlüsselvergleich mit weniger als O (n logn) Zeit basiert und die BST zum Sequenzteil dominiert. (Es gibt eine O (n) -Haufenkonstruktion.) Ich würde es für fair (wenn auch sinnlos) halten, zu behaupten, dass Haufen nahezu unsortiert und BSTs sortiert sind.
Graubart
Was ich hier zu erklären versuche, ist, dass wenn Sie eine BST und auch einen Haufen von n Elementen haben =>, alle Elemente in sortierter Reihenfolge aus beiden Datenstrukturen gedruckt werden können und BST dies in O (n) Zeit (Inorder Traversal) tun kann ), während Heap O (n logn) Zeit in Anspruch nehmen würde. Ich verstehe nicht, was Sie hier sagen wollen. Wie sagt man, dass BST Ihnen eine sortierte Reihenfolge in O (n logn) gibt?
CODError
Ich denke, Sie denken auch darüber nach, wie viel Zeit für den Bau eines BST und eines Heaps benötigt wird. Aber ich gehe davon aus, dass Sie es bereits haben, dass Sie es im Laufe der Zeit erstellt haben und jetzt das sortierte Ergebnis erhalten möchten. Ich verstehe deinen Standpunkt nicht?
CODError
1
Bearbeitet ... Ich hoffe du bist jetzt zufrieden; p und gib eine +1 wenn es richtig ist.
CODError
1

Das Einfügen aller n Elemente aus einem Array in BST dauert O (n logn). n Elemente in einem Array können in O (n) -Zeit in einen Heap eingefügt werden. Das gibt Heap einen klaren Vorteil

AMR
quelle
0

Heap garantiert nur, dass Elemente auf höheren Ebenen größer (für Max-Heap) oder kleiner (für Min-Heap) sind als Elemente auf niedrigeren Ebenen

Ich liebe die obige Antwort und setze meinen Kommentar nur spezifischer auf meine Bedürfnisse und Verwendung. Ich musste die Liste der n Standorte ermitteln lassen, um die Entfernung von jedem Standort zu einem bestimmten Punkt zu ermitteln, z. B. (0,0), und dann die am-Standorte mit geringerer Entfernung zurückgeben. Ich habe die Prioritätswarteschlange verwendet, die Heap ist. Um Entfernungen zu finden und einen Haufen einzulegen, brauchte ich n (log (n)) n-Stellen log (n) für jede Einfügung. Um m mit kürzesten Entfernungen zu erhalten, wurden m (log (n)) m-Stellen log (n) Löschungen des Aufhäufens benötigt.

Wenn ich dies mit BST tun müsste, hätte ich n (n) Worst-Case-Einfügung benötigt. (Angenommen, der erste Wert ist sehr kleiner und alle anderen werden nacheinander länger und länger und der Baum erstreckt sich nur zum rechten oder linken Kind im Falle von immer kleiner. Die min hätte O (1) Zeit in Anspruch genommen, aber ich musste wieder ausbalancieren. Aus meiner Situation und allen obigen Antworten habe ich also erhalten, wenn Sie erst nach den Werten bei min oder max Priorität gehen für Haufen.

Sahib Khan
quelle