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?
quelle
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?
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.
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äre Suchbäume (BST) folgen einer bestimmten Reihenfolge (Vorbestellung, Reihenfolge, Nachbestellung) zwischen Geschwisterknoten. Der Baum muss im Gegensatz zu Haufen sortiert werden:
quelle
Zusammenfassung
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,n
für dynamischen Array-HeapVorteile des binären Heap gegenüber einem BST
Die durchschnittliche Zeit für das Einfügen in einen binären Heap beträgt
O(1)
für BSTO(log(n))
. Dies ist das Killer - Feature von Halden.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 nicht asymptotischer Leistung möglicherweise nicht praktikabel sind: https://stackoverflow.com/questions/30782636 / Are-Fibonacci-Haufen-oder-Brodal-Warteschlangen-verwendet-in-der-Praxis-überallBinäre Heaps können effizient entweder auf dynamischen Arrays oder auf zeigerbasierten Bäumen implementiert werden , BST nur auf zeigerbasierten Bäumen. Für den Heap können wir also die platzsparendere Array-Implementierung wählen, wenn wir uns gelegentliche Latenzen bei der 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 die Killerfunktion von BSTs.Bei Heap ist dies
O(n)
im Allgemeinen der Fall, mit Ausnahme des größten ElementsO(1)
."Falscher" Vorteil von Heap gegenüber BST
Haufen ist
O(1)
zu finden, max, BSTO(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:
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 ) undstd::priority_queue
( Dynamic Array Heap ) Insert verglichen, um zu sehen, ob ich bezüglich der Einfügezeiten recht hatte, und das habe ich bekommen: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.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 FallO(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 + 1struct
Zeiger).Baum-BSTs würden auch weitere Ausgleichsinformationen benötigen, z. B. Schwarz-Rot.
Die dynamische Array-Implementierung kann
2n
unmittelbar nach einer Verdopplung eine Größe haben . So wird es im Durchschnitt sein1.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:
O(1)
Schlimmster Fall, da wir Zeiger auf die Elemente haben und das Update wirklich einfach istO(1)
Durchschnitt, also schlechter als verknüpfte Liste. Kompromiss für allgemeinere Einfügeposition.O(n)
für beideEin 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:
Siehe auch
Ähnliche Frage zu CS: Was ist der Unterschied zwischen einem binären Suchbaum und einem binären Heap?
quelle
Bei der Datenstruktur muss man die Betroffenheitsebenen unterscheiden.
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.
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
BST
Schlü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.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).
quelle
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.
quelle