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

Antwort

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 möchten, 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)). Einfügen ist O (logN) für beide Strukturen. Wenn Sie sich nur für findMin / findMax interessieren (z. B. prioritätsbezogen), gehen Sie mit heap. Wenn Sie möchten Alles sortiert, gehen Sie mit BST.

von xysun

Kommentare

  • Ich denke, BST ist besser in findMin & findMax stackoverflow .com / a / 27074221/764592
  • Ich denke, dies ist nur eine Kommunikation auf Missverständnis. Ein Binärbaum kann leicht modifiziert werden, um Min und Max zu finden, wie von Yeo angegeben. Dies ist tatsächlich eine Einschränkung des Heaps: Der einzige effiziente Fund ist min oder max. Der wahre Vorteil des Heaps ist die durchschnittliche Einfügung von O (1) , wie ich erkläre: stackoverflow.com/a/29548834/895245
  • Gemäß dieses Videos können Sie größere Werte auf einer niedrigeren Ebene haben, solange die größere nicht von der unteren abstammt.
  • Heap ist von Wurzel zu Blatt und BST von links nach rechts sortiert.
  • Was ist, wenn ich den Median in konstanter Zeit finden und den Median in logarithmischer Zeit entfernen möchte? Für welche Datenstruktur soll ich mich entscheiden? funktioniert die Implementierung von MinHeap? Bitte vorschlagen.

Antwort

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 ist BST == Balanced BST, da Unbalanced asymptotisch saugt
  • **: Verwenden einer in dieser Antwort erläuterten trivialen Modifikation
  • ***: log(n) für den Zeigerbaum-Heap n für dynamischen Array-Heap

Vorteile des binären Heaps gegenüber einer BST

Vorteil von BST gegenüber binärem Heap

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

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

„Falscher“ Vorteil des Heaps gegenüber BST

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

    Dies ist ein häufiges 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. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (erwähnt von Yeo ).

    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
  • Heap-Einfügung beginnt von unten , BST muss von oben beginnen

In einem binären Heap wird auch der Wert an einem bestimmten Index erhöht O(1) aus demselben Grund. Wenn Sie dies jedoch tun möchten, möchten Sie wahrscheinlich einen zusätzlichen Index für Heap-Vorgänge auf dem neuesten Stand halten. https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu zB für Dijkstra. Ohne zusätzliche Zeitkosten möglich.

Benchmark zum Einfügen von GCC C ++ – Standardbibliotheken auf realer Hardware

Ich habe das C ++ std::set ( Rot-Schwarz-Baum BST ) und ( dynamischer Array-Heap ) einfügen, um zu sehen, ob ich mit den Einfügezeiten Recht hatte, und Folgendes habe ich erhalten:

Geben Sie hier die Bildbeschreibung ein.

  • Benchmark-Code
  • Plot-Skript
  • 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)

Also klar:

Benchmark zum Einfügen einer GCC C ++ – Standardbibliothek auf gem5

gem5 ist ein vollständiger Systemsimulator und bietet daher eine unendlich genaue Uhr mit m5 dumpstats. Deshalb habe ich versucht, damit die Timings für einzelne Einfügungen zu schätzen.

Geben Sie hier die Bildbeschreibung ein

Interpretation:

  • 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 der Speicherzugriffslatenz entsprechen, die für immer höhere Einfügungen durchgeführt wird.

  • TODO Ich kann die BST nicht vollständig so interpretieren, wie sie ist sieht nicht so logarithmisch und etwas konstanter aus.

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

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

BST kann auf einem Array

Heap Operationen müssen nur einen einzelnen Ast hoch oder runter sprudeln, also O(log(n)) Worst-Case-Swaps, O(1) Durchschnitt.

Um eine BST im Gleichgewicht zu halten, sind Baumrotationen erforderlich, die das obere Element durch ein anderes ersetzen können, und das Verschieben des gesamten Arrays (O(n)).

Heaps können effizient in einem Array implementiert werden.

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

Es gibt keine Ausgleichsoperationen wie BST.

min löschen ist die besorgniserregendste Operation muss von oben nach unten sein. Dies kann jedoch immer durch „Durchsickern“ eines einzelnen Zweigs des Heaps 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 der Asymptotik O (1) durchschnittliche Einfügung, die Heaps bereitstellen, 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 implementiert werden über Zeigerhaufen: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

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

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

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

  • Die Implementierung des dynamischen Arrays kann unmittelbar nach einer Verdoppelung die Größe 2n haben. Im Durchschnitt wird es also 1.5n sein.

Andererseits hat der Baumhaufen eine bessere Worst-Case-Einfügung. da das Kopieren des dynamischen Backing-Arrays auf die doppelte Größe O(n) den schlimmsten Fall erfordert, während der Baumheap nur neue kleine Zuordnungen für jeden Knoten vornimmt.

Trotzdem das Backing Die Array-Verdopplung wird O(1) amortisiert, sodass eine maximale Latenz berücksichtigt wird. Hier erwähnt .

Philosophie

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

    Der oberste Knoten einer BST ist das mittlere Element Dies erfordert globales Wissen (um zu 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 behalten eine lokale Eigenschaft zwischen übergeordneten und direkten untergeordneten Elementen (übergeordnete> untergeordnete Elemente) bei.

    Die Kopfnote eines Heapspeichers ist das große Element erfordert nur lokales Wissen, um zu pflegen (Kenntnis Ihrer Eltern).

Vergleichen von BST mit Heap und 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

  • Heap: 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 eine ungeordnete Menge sein, keine effiziente Sortiermaschine. weil das 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 in jeder Position enden. 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 mit allgemeinerer 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 beibehalten.

Dies kann verwendet werden, um einen LRU-Cache zu implementieren . Genau wie für 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 das asymptotische Einfügen und Finden Die Zeiten für alle Datenstrukturen, die üblicherweise als „ausgeglichene BSTs“ klassifiziert werden, die ich bisher gesehen habe, sind die gleichen. Unterschiedliche BBSTs haben unterschiedliche Kompromisse. Ich habe dies noch nicht vollständig untersucht, aber es wäre gut, es zusammenzufassen Diese Kompromisse hier:

  • Rot-Schwarzer Baum . Scheint ab 2019 das am häufigsten verwendete BBST zu sein, z. Es wird von der GCC 8.3.0 C ++ – Implementierung verwendet.
  • AVL-Baum . Scheint etwas ausgeglichener zu sein als BST, daher könnte es besser sein, die Latenz zu finden, auf Kosten etwas teurerer Funde.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 ausgeglichen. Ä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 eine sehr unterschiedliche Anzahl von Nachkommen haben. „
  • WAVL . Das Originalpapier erwähnt die Vorteile dieser Version in Bezug auf die Grenzen für Neuausgleichs- und Rotationsvorgänge.

Siehe auch

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

Kommentare

  • Gute Antwort . Übliche Anwendung von Heap sind Median, k min, top k Elemente. Für diese häufigste Operation entfernen Sie min und fügen Sie dann ein (normalerweise haben wir einen kleinen Haufen mit wenigen reinen Einfügeoperationen). So scheint es in der Praxis, dass diese Algorithmen BST nicht übertreffen.
  • Außergewöhnliche Antwort !!! Durch die Verwendung von deque als zugrunde liegende Heap-Struktur können Sie die Größenänderungszeiten drastisch reduzieren, obwohl dies immer noch O (n) der schlimmste Fall ist, da ein (kleineres) Array von Zeigern auf Chunks neu zugewiesen werden muss.

Antwort

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 Max-Heap müssen die untergeordneten Knoten jedes Knotens kleiner sein als er selbst. Dies ist das Gegenteil für einen Min-Heap:

Binärer Max-Heap

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

Binärer Suchbaum

BST haben einen Durchschnitt von $ O (\ log n) $ zum Einfügen, Löschen und Suchen.
Binäre Heaps haben einen durchschnittlichen $ O (1) $ für findMin / findMax und $ O (\ log n) $ zum Einfügen und Löschen.

Kommentare

  • @FrankW Extraktion ist $ O (\ log n) $, nein?

Antwort

Bei der Datenstruktur muss man die betroffenen Ebenen unterscheiden.

  1. Die abstrakten Datenstrukturen (gespeicherte Objekte, ihre Operationen) in diesem q Fragen sind anders. 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 größten Priorität.

  2. Die konkrete Implementierung der Strukturen. Hier sind auf den ersten Blick beide (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 BST werden die Schlüssel von links nach rechts angeordnet, in einem Heap von oben nach unten.) Wie IPlant korrekt 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 hingegen hat eine effiziente Implementierung unter Verwendung eines Arrays (genau wegen der eingeschränkten Struktur).

Antwort

Zusätzlich zu den vorherigen Antworten muss der Heap die Heap-Struktureigenschaft haben ;; Der Baum muss voll sein, und die unterste Schicht, die nicht immer voll sein kann, muss ganz links bis ganz rechts ohne Lücken gefüllt sein.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.