Heap vs Binary Search Tree (BST)

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?

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:

• Papier: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• WSU-Folien: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

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:

• 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.

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

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.

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.

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.

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 ... :)

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.

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

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.