Was ist der Unterschied zwischen einem binären Suchbaum und einem binären Heap?

91

Diese beiden scheinen sehr ähnlich zu sein und haben eine fast identische Struktur. Was ist der Unterschied? Was sind die Zeitkomplexitäten für verschiedene Operationen von jedem?

Piperchester
quelle

Antworten:

63

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. von Dante ist kein Geek

Heap ist besser bei findMin / findMax (O (1)), während BST bei allen Funden gut ist (O (logN)). Insert ist O (logN) für beide Strukturen. Wenn Sie sich nur für findMin / findMax interessieren (z. B. prioritätsbezogen), entscheiden Sie sich für heap. Wenn Sie alles sortiert haben möchten, wählen Sie BST.

von xysun

Ali786
quelle
Ich denke, BST ist besser in findMin & findMax stackoverflow.com/a/27074221/764592
Yeo
10
Ich denke, das ist nur ein verbreiteter Irrtum. Ein binärer Baum 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 Heaps ist O (1) durchschnittliche Einfügung, wie ich erkläre: stackoverflow.com/a/29548834/895245
Ciro Santilli Am
Laut diesem Video können Sie größere Werte auf einer niedrigeren Ebene haben, solange der größere nicht von dem niedrigeren abgeleitet ist.
whoan
Heap ist von Wurzel zu Blatt sortiert und BST ist von links nach rechts sortiert.
Deep Joshi
34

Sowohl binäre Suchbäume als auch binäre Heaps sind baumbasierte Datenstrukturen.

Bei Heaps müssen die Knoten Vorrang vor ihren untergeordneten Knoten haben. In einem maximalen Heap müssen die Kinder jedes Knotens kleiner sein als sie selbst. Dies ist das Gegenteil für einen kleinen Haufen:

Binärer maximaler Haufen

Binäre Suchbäume (BST) folgen einer bestimmten Reihenfolge (Vorbestellung, Reihenfolge, Nachbestellung) zwischen Geschwisterknoten. Der Baum muss im Gegensatz zu Haufen sortiert werden:

Binärer Suchbaum

O(logn)
O(1)O(logn)

Piperchester
quelle
1
O(logn)
32

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)

Mit Ausnahme von Einfügen stimmen alle Durchschnittszeiten in dieser Tabelle mit den schlechtesten Zeiten überein.

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

Vorteile des binären Heap gegenüber einem BST

Vorteil von BST gegenüber binärem Heap

  • Suche nach beliebigen Elementen ist O(log(n)). Dies ist die Killerfunktion von BSTs.

    Bei Heap ist dies O(n)im Allgemeinen der Fall, mit Ausnahme des größten Elements O(1).

"Falscher" Vorteil von Heap gegenüber BST

  • Haufen ist O(1)zu finden, max, BST 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 zu aktualisieren, wann immer dieses Element geändert werden könnte: Wenn ein größerer Swap eingefügt wird, muss beim Entfernen der zweitgrößte gefunden werden. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation ( von Yeo erwähnt ).

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

Durchschnittliche binäre Heap-Einfügung ist O(1)

Quellen:

Intuitives Argument:

  • Die untersten Baumebenen haben exponentiell mehr Elemente als die obersten Ebenen, so dass fast sicher ist, dass sich neue Elemente am unteren Rand befinden
  • Heap-Einfügung beginnt von unten , BST muss von oben beginnen

In einem binären Heap ist das Erhöhen des Werts bei einem bestimmten Index ebenfalls O(1)der gleiche Grund. Wenn Sie dies jedoch tun möchten, ist es wahrscheinlich, dass Sie einen zusätzlichen Index für Heap-Vorgänge auf dem neuesten Stand halten möchten. Https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease- Tastenbedienung-für-min-Heap-basierte-Prioritätswarteschlange zB für Dijkstra. Ohne Mehrkosten möglich.

GCC C ++ Standard Library Insert Benchmark auf echter Hardware

Ich habe das C ++ std::set( Red-Black Tree BST ) und std::priority_queue( Dynamic Array Heap ) Insert verglichen, um zu sehen, ob ich bezüglich der Einfügezeiten recht hatte, und das habe ich bekommen:

Bildbeschreibung hier eingeben

  • Benchmark-Code
  • Handlungsskript
  • Plotdaten
  • Getestet auf 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 16GiB , 2400 Mbit / s), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3.000 MB / s)

So klar:

  • Die Zeit für das Einfügen des Heapspeichers ist im Grunde genommen konstant.

    Wir können deutlich sehen, wie die Größe von Punkten für dynamische Arrays geändert wird. Da wir im Durchschnitt alle 10.000 Inserts verwenden , um alles über dem Systemrauschen zu sehen , sind diese Peaks tatsächlich etwa 10.000 Mal größer als gezeigt!

    Das gezoomte Diagramm schließt im Wesentlichen nur die Punkte zur Größenänderung des Arrays aus und zeigt, dass fast alle Einfügungen unter 25 Nanosekunden fallen.

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

  • Detaillierte Analyse von BST vs Hashmap unter: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

GCC C ++ Standard Library Insert Benchmark auf gem5

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

Bildbeschreibung hier eingeben

Interpretation:

  • Haufen ist immer noch konstant, aber jetzt sehen wir genauer, dass es ein paar 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 die BST nicht wirklich vollständig interpretieren, da sie nicht so logarithmisch und etwas konstanter aussieht.

    Mit diesem größeren Detail können wir jedoch sehen, dass wir auch ein paar verschiedene Linien sehen können, 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 runterblasen, daher sind O(log(n))Swaps im schlimmsten Fall O(1)durchschnittlich.

Um einen BST im Gleichgewicht zu halten, sind Baumrotationen erforderlich, die das oberste Element durch ein anderes ersetzen können. Außerdem muss das gesamte Array um ( O(n)) verschoben werden .

Heaps können auf einem Array effizient implementiert werden

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

Es gibt keine Ausgleichsoperationen wie BST.

Delete min ist die beunruhigendste Operation, da es von oben nach unten erfolgen muss. Dies kann jedoch immer durch "Durchsickern" 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 Knoten, den Sie entfernen, einen einzelnen Knoten einfügen, verlieren Sie den Vorteil der asymptotischen O (1) -Durchschnitts-Einfügung, die Heaps bieten, da der Löschvorgang dominieren würde, und Sie können auch eine BST verwenden. Dijkstra aktualisiert Knoten jedoch mehrmals für jede Entfernung, sodass wir in Ordnung sind.

Dynamische Array-Heaps vs. Zeigerbaum-Heaps

Heaps können effizient über Pointer-Heaps implementiert werden: https://stackoverflow.com/questions/19720438/is-it-possible-make-efficient-pointer-based-binary-heap-implementations

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

  • Die Baumimplementierung muss drei Zeiger für jedes Element speichern: übergeordnetes Element, linkes untergeordnetes Element und rechtes untergeordnetes Element. Die Speichernutzung ist also immer 4n(3 Baumzeiger + 1 structZeiger).

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

  • Die dynamische Array-Implementierung kann 2nunmittelbar nach einer Verdopplung eine Größe haben . So wird es im Durchschnitt sein 1.5n.

Auf der anderen Seite hat der Baum-Heap eine bessere Einfügung im ungünstigsten Fall, da das Kopieren des dynamischen Sicherungs-Arrays auf die doppelte Größe den O(n)ungünstigsten Fall darstellt, während der Baum-Heap nur neue kleine Zuordnungen für jeden Knoten vornimmt.

Dennoch wird die Verdopplung des Backing-Arrays O(1)amortisiert, sodass es auf eine maximale Latenzzeit ankommt. Hier erwähnt .

Philosophie

  • BSTs behalten eine globale Eigenschaft zwischen einem übergeordneten Element und allen untergeordneten Elementen bei (links kleiner, rechts größer).

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

    Diese globale Eigenschaft ist in der Pflege teurer (log n insert), bietet jedoch leistungsfähigere Suchfunktionen (log n search).

  • Haufen behalten eine lokale Eigenschaft zwischen Eltern und direkten Kindern (Eltern> Kinder) bei.

    Die Kopfnote eines Haufens ist das große Element, für dessen Aufrechterhaltung nur lokales Wissen erforderlich ist (das Wissen Ihres Elternteils).

Doppelt verknüpfte Liste

Eine doppelt verknüpfte Liste kann als Teilmenge des Heaps angesehen werden, bei 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 Objekt kann an einer beliebigen Position landen. Weniger restriktiv als verknüpfte Liste.
    • Zeit:
      • doppelt verknüpfte Liste: O(1)Schlimmster Fall, da wir Zeiger auf die Elemente haben und das Update wirklich einfach ist
      • binärer Heap: O(1)Durchschnitt, also schlechter als verknüpfte Liste. Kompromiss für 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 verschoben. So können wir den genauen Zeitstempel sogar ganz vergessen und die Position in der Liste einfach als Priorität beibehalten.

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 in der Liste behalten, um schnell herauszufinden, welcher Knoten aktualisiert werden soll.

Vergleich verschiedener Balanced BST

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

  • Rot-schwarzer Baum . Scheint die ab 2019 am häufigsten verwendete BBST zu sein, z. B. die, die von der GCC 8.3.0 C ++ -Implementierung verwendet wird
  • AVL-Baum . Scheint ein bisschen ausgeglichener zu sein als BST, daher könnte es besser sein, die Latenz zu finden, auf Kosten etwas teurerer Fundstücke. Wiki fasst zusammen: "AVL-Bäume werden oft mit rot-schwarzen Bäumen verglichen, weil beide die gleiche Menge von Operationen unterstützen und [die gleiche] Zeit für die Grundoperationen benötigen. Für suchintensive Anwendungen 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 mu <1/2, das heißt, Geschwisterknoten können sehr viele haben unterschiedliche Anzahl von Nachkommen. "
  • WAVL . In der Originalarbeit werden die Vorteile dieser Version in Bezug auf die Grenzen der Auswucht- und Rotationsvorgänge erwähnt.

Siehe auch

Ähnliche Frage zu CS: Was ist der Unterschied zwischen einem binären Suchbaum und einem binären Heap?

Ciro Santilli ist ein Schauspieler
quelle
1
Gute Antwort. Häufige Anwendung von Heap sind Median-, kmin- und Top-k-Elemente. Für diese am häufigsten ausgeführten Operationen entfernen Sie min und fügen dann ein (normalerweise haben wir einen kleinen Heap mit wenigen reinen Einfügeoperationen). Es scheint also wie in der Praxis, dass diese Algorithmen BST nicht übertreffen.
Yura
1
Außergewöhnliche Antwort !!! Indem Sie deque als zugrunde liegende Heap-Struktur verwenden, können Sie die Größenänderungszeiten drastisch reduzieren, obwohl dies immer noch der schlimmste Fall ist, da ein (kleineres) Array von Zeigern auf Chunks neu zugeordnet werden muss.
Bulat
13

Bei der Datenstruktur muss man die Betroffenheitsebenen unterscheiden.

  1. Die abstrakten Datenstrukturen (gespeicherte Objekte, ihre Operationen) in dieser Frage sind unterschiedlich. Einer implementiert eine Prioritätswarteschlange, der andere eine Menge. Eine Prioritätswarteschlange ist nicht daran interessiert, ein beliebiges Element zu finden, sondern nur das mit der höchsten Priorität.

  2. Die konkrete Umsetzung der Strukturen. Hier sind beide auf den ersten Blick (binäre) Bäume mit unterschiedlichen strukturellen Eigenschaften. Sowohl die relative Reihenfolge der Schlüssel als auch die möglichen globalen Strukturen unterscheiden sich. (Etwas ungenau, in einem BSTSchlüssel sind sie von links nach rechts angeordnet, in einem Heap von oben nach unten.) Wie IPlant richtig bemerkt, sollte ein Heap auch "vollständig" sein.

  3. Es gibt einen letzten Unterschied in der Implementierung auf niedriger Ebene . Ein (unsymmetrischer) binärer Suchbaum hat eine Standardimplementierung unter Verwendung von Zeigern. Ein binärer Heap hat dagegen eine effiziente Implementierung unter Verwendung eines Arrays (gerade wegen der eingeschränkten Struktur).

Hendrik Jan
quelle
1

Zusätzlich zu den vorherigen Antworten muss der Heap über die Eigenschaft Heap-Struktur verfügen. Der Baum muss voll sein und die unterste Schicht, die nicht immer voll sein kann, muss von links nach rechts ohne Lücken gefüllt sein.

lAnlage
quelle