Haufen (Datenstruktur)

Beispiel von a binär Max-heap mit Knotenschlüssel sind Zahlen zwischen 1 und 100

Im Informatik, a Haufen ist spezialisiert Baum-basierend Datenstruktur Welches ist im Wesentlichen ein Fast fertig[1] Baum, der das erfüllt Haufen Eigentum: in einem Max Haufenfür jede bestimmte Knoten C, wenn p ein übergeordneter Knoten von C ist, dann die Schlüssel (das Wert) von p ist größer oder gleich dem Schlüssel von C in a Min Heap, Der Schlüssel von P ist weniger oder gleich dem Schlüssel von C.[2] Der Knoten an der "Oberseite" des Haufens (ohne Eltern) heißt das Wurzel Knoten.

Der Haufen ist eine maximal effiziente Implementierung von a Zusammenfassung Datentyp genannt Prioritätswarteschlangeund in der Tat werden vorrangige Warteschlangen oft als "Haufen" bezeichnet, unabhängig davon, wie sie implementiert werden können. Auf einem Haufen wird das höchste (oder niedrigste) Prioritätselement immer am Wurzel gespeichert. Ein Haufen ist jedoch keine sortierte Struktur; Es kann als teilweise geordnet angesehen werden. Ein Heap ist eine nützliche Datenstruktur, wenn es notwendig ist, das Objekt wiederholt mit der höchsten (oder niedrigsten) Priorität zu entfernen oder wenn Insertionen mit Entfernungen des Stammknotens durchsetzt werden müssen.

Eine häufige Umsetzung eines Haufens ist die Binärhaufen, in denen der Baum a ist Binärbaum (Siehe Abbildung). Die Heap -Datenstruktur, insbesondere der binäre Haufen, wurde durch eingeführt von J. W. J. Williams 1964 als Datenstruktur für die Haufen Sortieren von Algorithmus.[3] Haufen sind auch in mehreren effizienten entscheidenden Graphalgorithmen wie zum Beispiel Dijkstra -Algorithmus. Wenn ein Haufen ein kompletter binärer Baum ist, hat er eine kleinstmögliche Höhe - ein Haufen mit N Knoten und a Zweige für jeden Knoten haben immer Protokolla N Höhe.

Beachten Sie, dass, wie in der Grafik gezeigt, keine implizite Ordnung zwischen Geschwistern oder Cousins ​​und keine implizite Sequenz für eine gibt In-Ordnung-Traversal (wie es in z. B. a sein würde, a Binärer Suchbaum). Die oben erwähnte Heap -Beziehung gilt nur zwischen Knoten und ihren Eltern, Großeltern usw. Die maximale Anzahl von Kindern, die jeder Knoten aufweist, hängt von der Art des Haufens ab.

Operationen

Die gemeinsamen Operationen mit Haufen sind:

Basic
  • Fundmax (oder Fund-min): Finden Sie ein maximales Element eines Max-HEAP bzw. ein Minimum eines Minimas (a.k.a. spähen)
  • Einfügung: Hinzufügen eines neuen Schlüssels zum Haufen (a.k.a., drücken[4])
  • Extraktmax (oder Extrakt-min): Gibt den Knoten des Maximalwerts aus einem maximalen Haufen [oder Mindestwert aus einem minem Haufen] zurück, nachdem er ihn aus dem Haufen entfernt hat (a.k.a.,. Pop[5])
  • Löschen-Max (oder lösche min): Entfernen des Wurzelknotens eines maximalen Heaps (oder min -Haufens)
  • ersetzen: Pop Root und drücken Sie einen neuen Schlüssel. Effizienter als POP, gefolgt von Push, da nur einmal und nicht zweimal ausgleichen und für Haufen fester Größe geeignet sind.[6]
Schaffung
  • heap erstellen: Erstellen Sie einen leeren Haufen
  • häufern: Erstellen Sie einen Haufen aus angegebenem Elementen
  • verschmelzen (Union): Mit zwei Haufen einen gültigen neuen Heap bildet, der alle Elemente von beiden enthält, die die ursprünglichen Haufen erhalten.
  • verschmelzen: Mit zwei Haufen bilden ein gültiger neuer Haufen, der alle Elemente von beiden enthält und die ursprünglichen Haufen zerstört.
Inspektion
  • Größe: Geben Sie die Anzahl der Elemente im Haufen zurück.
  • ist leer: Return true, wenn der Haufen leer ist, sonst falsch.
Intern
  • Erhöhungschlüssel oder Abnahme: Aktualisieren eines Schlüssels innerhalb eines Max- bzw. minheap
  • löschen: Löschen Sie einen willkürlichen Knoten (gefolgt von dem Verschieben des letzten Knotens und Sieben, um den Haufen aufrechtzuerhalten)
  • sieben: Bewegen Sie einen Knoten im Baum so lange wie nötig; Wird verwendet, um den Haufen Zustand nach dem Einsetzen wiederherzustellen. Genannt "sieben", weil der Knoten den Baum hinaufbewegt, bis er die richtige Ebene erreicht, wie in a Sieb.
  • sieben: Bewegen Sie einen Knoten in den Baum, ähnlich dem Sift-Up; Wird verwendet, um den Haufen Zustand nach dem Löschen oder nach dem Austausch wiederherzustellen.

Implementierung

Haufen werden normalerweise mit einem implementiert Array, folgendermaßen:

  • Jedes Element im Array repräsentiert einen Knoten des Haufens, und
  • Die Eltern / Kinderbeziehung ist implizit definiert nach den Elementenindizes im Array.
Beispiel für einen vollständigen binären Max-heap mit Knotenschlüssel sind Ganzzahlen von 1 bis 100 und wie es in einem Array gespeichert wird.

Für ein BinärhaufenIm Array enthält der erste Index das Stammelement. Die nächsten beiden Indizes des Arrays enthalten die Kinder der Wurzel. Die nächsten vier Indizes enthalten die vier Kinder der beiden Kinderknoten der Wurzel und so weiter. Daher bei einem Knoten am Index gegeben i, seine Kinder sind bei Indizes und und sein Elternteil ist im Index ⌊ (i−1)/2⌋. Dieses einfache Indexierungsschema macht es effizient, den Baum "nach oben" oder "unten" zu bewegen.

Das Ausgleich eines Haufens erfolgt durch Sift- oder Sift-Down-Operationen (Austauschelemente, die nicht in Ordnung sind). Da wir einen Haufen aus einem Array erstellen können, ohne zusätzlichen Speicher zu benötigen (zum Beispiel für die Knoten), Haufen Kann verwendet werden, um ein Array an Ort zu sortieren.

Nachdem ein Element in einen Haufen eingefügt oder gelöscht wurde, kann die Heap-Eigenschaft verletzt werden und der Haufen muss durch Austausch von Elementen innerhalb des Arrays erneut ausgewogen werden.

Obwohl unterschiedliche Art von Haufen die Operationen unterschiedlich implementieren, ist der häufigste Weg wie folgt:

  • Einfügung: Fügen Sie das neue Element am Ende des Haufens im ersten verfügbaren Freiraum hinzu. Wenn dies gegen das Heap -Eigentum verstößt, sieben Sie das neue Element (schwimmen Betrieb) bis das Heap -Eigentum wiederhergestellt wurde.
  • Extraktion: Entfernen Sie die Wurzel und fügen Sie das letzte Element des Haufens in die Wurzel ein. Wenn dies gegen das Heap -Eigentum verstößt, sieben Sie die neue Wurzel (Waschbecken Betrieb) Um das Heap -Eigentum wiederherzustellen.
  • Ersatz: Entfernen Sie die Wurzel und setzen Sie die Neu Element in der Wurzel und sieben Sie nach unten. Im Vergleich zur Extraktion gefolgt von Insertion vermeidet dies einen Schritt -Up -Schritt.

Bau eines binären (oder d-ary) Haufen aus einer bestimmten Reihe von Elementen kann in der linearen Zeit mit dem Klassiker durchgeführt werden Floyd -Algorithmusmit der schlimmsten Fallzahl von Vergleiche entspricht 2N - 2s2(N) - e2(N) (für einen binären Haufen), wo s2(N) ist die Summe aller Ziffern der binären Darstellung von N und e2(N) ist der Exponent von 2 bei der Primfaktorisierung von N.[7] Dies ist schneller als eine Folge von aufeinanderfolgenden Insertionen in einen ursprünglich leeren Haufen, der logarithmisch linear ist.[a]

Varianten

Vergleich der theoretischen Grenzen für Varianten

Hier sind Zeitkomplexität[8] von verschiedenen Heap -Datenstrukturen. Funktionsnamen nehmen eine max-heap an. Für die Bedeutung von "O(f)" und "Θ(f)" sehen Big O Notation.

Betrieb Fundmax Löschen-Max Einfügung Erhöhungschlüssel verschmelzen
Binär[8] Θ(1) Θ(Protokolln)) O(Protokolln)) O(Protokolln)) Θ(n))
Linke Θ(1) Θ(Protokoll n)) Θ(Protokoll n)) O(Protokoll n)) Θ(Protokoll n))
Binomial[8][9] Θ(1) Θ(Protokoll n)) Θ(1)[b] Θ(Protokoll n)) O(Protokolln)[c]
Fibonacci[8][10] Θ(1) O(Protokolln)[b] Θ(1) Θ(1)[b] Θ(1)
Paarung[11] Θ(1) O(Protokoll n)[b] Θ(1) o(Protokolln)[b][d] Θ(1)
Brodal[14][e] Θ(1) O(Protokolln)) Θ(1) Θ(1) Θ(1)
Rangpaarung[16] Θ(1) O(Protokoll n)[b] Θ(1) Θ(1)[b] Θ(1)
Strenge Fibonacci[17] Θ(1) O(Protokoll n)) Θ(1) Θ(1) Θ(1)
2–3 Haufen[18] O(Protokoll n)) O(Protokoll n)[b] O(Protokoll n)[b] Θ(1) ?
  1. ^ Jede Einfügung nimmt O (log (log (log)k)) In der vorhandenen Größe des Haufens also also . Seit , ein konstanter Faktor (die Hälfte) dieser Einfügungen liegt innerhalb eines konstanten Faktors des Maximums, sodass wir asymptotisch annehmen können ; formell ist die Zeit . Dies kann auch leicht aus gesehen werden Stirlings Annäherung.
  2. ^ a b c d e f g h i Abgeschriebene Zeit.
  3. ^ n ist die Größe des größeren Haufens.
  4. ^ Untergrenze von [12] Obergrenze von [13]
  5. ^ Brodal und Okasaki beschreiben später a hartnäckig Variante mit den gleichen Grenzen, mit Ausnahme des Abnahmeschlüssels, der nicht unterstützt wird. Haufen mit n Elemente können in Bottom-up in konstruiert werden in O(n).[15]

Anwendungen

Die Heap -Datenstruktur hat viele Anwendungen.

  • Haufen: Eine der besten Sortiermethoden, die an Ort und Stelle sind und ohne quadratische Worst-Case-Szenarien.
  • Auswahlalgorithmen: Ein Heap ermöglicht den Zugriff auf das min- oder maximale Element in konstanter Zeit, und andere Auswahlen (z. B. Median oder KTH-Element) können in sublinearer Zeit für Daten in einem Haufen erfolgen.[19]
  • Graphalgorithmen: Durch die Verwendung von Haufen als interne Durchlaufdatenstrukturen wird die Laufzeit durch Polynomreihenfolge verkürzt. Beispiele für solche Probleme sind Prims Minimal-Spanning-Tree-Algorithmus und Dijkstra's kürzester Pfadalgorithmus.
  • Prioritätswarteschlange: Eine vorrangige Warteschlange ist ein abstraktes Konzept wie "eine Liste" oder "eine Karte". So wie eine Liste mit einer verknüpften Liste oder einem Array implementiert werden kann, kann eine vorrangige Warteschlange mit einem Haufen oder einer Vielzahl anderer Methoden implementiert werden.
  • K-Way-Zusammenführung: Eine Heap-Datenstruktur ist nützlich, um viele bereits sortierte Eingabestreams in einen einzelnen Sortierten-Ausgangsstrom zu verschmelzen. Beispiele für das Verschmelzungsbedarf umfassen externe Sortier- und Streaming -Ergebnisse aus verteilten Daten wie einem strukturierten Zusammenführungsbaum. Die innere Schleife erhält das min-Element, ersetzt durch das nächste Element für den entsprechenden Eingangsstrom und führt dann einen Sift-Down-Haufen-Betrieb durch. (Alternativ die Ersetzungsfunktion.) (Verwenden von Extraktmax und Einfügenfunktionen einer Prioritätswarteschlange sind viel weniger effizient.)
  • Bestellstatistik: Mit der Heap -Datenstruktur kann das kTH kleinste (oder größte) Element in einem Array effizient ermittelt werden.

Programmiersprache Implementierungen

  • Das C ++ Standardbibliothek Bietet die make_heap, push_heap und pop_heap Algorithmen für Haufen (normalerweise als binäre Haufen implementiert), die mit willkürlichem Zufallszugriff arbeiten Iteratoren. Es behandelt die Iteratoren als Verweis auf ein Array und verwendet die Array-to-Heap-Konvertierung. Es liefert auch den Containeradapter Prioritätswarteschlange, die diese Einrichtungen in einer containerähnlichen Klasse umwickelt. Es gibt jedoch keine Standardunterstützung für die Ersatz-, Sift-Up/Sift-Down- oder Abnahme-/Erhöhung-Key-Operationen.
  • Das Steigern Sie C ++ - Bibliotheken Fügen Sie eine Haufenbibliothek ein. Im Gegensatz zum STL unterstützt es eine Verringerung und erhöht den Betrieb und unterstützt zusätzliche Arten von Haufen: Speziell unterstützt es d-ary, Binomial, Fibonacci, Paarung und Schräghaufen.
  • Da ist ein Generische Heap -Implementierung zum C und C ++ mit D-Ary Heap und B-HEAP Unterstützung. Es bietet eine STL-ähnliche API.
  • Die Standardbibliothek der D Programmiersprache inklusive Std.Container.Binaryheap, was in Bezug auf Ds implementiert wird Bereiche. Instanzen können aus jedem konstruiert werden Random-Access-Bereich. Binaryheap enthüllt eine Eingabebereichschnittstelle Das ermöglicht die Iteration mit Ds integriert für jeden Aussagen und Integration in die von der Range basierende API der std.algorithmus Paket.
  • Zum Haskell dort ist der Daten.Heap Modul.
  • Das Java Plattform (da Version 1.5) eine binäre Heap -Implementierung mit der Klasse bietet Java.util.Priorityqueue in dem Java -Sammlungsrahmen. Diese Klasse implementiert standardmäßig einen Min-heap; Um einen max-heap zu implementieren, sollte der Programmierer einen benutzerdefinierten Komparator schreiben. Es gibt keine Unterstützung für Ersatz-, Sift-up/Sift-Down- oder Verringerung/Erhöhung-Key-Operationen.
  • Python hat ein Heapq Modul, das eine vorrangige Warteschlange unter Verwendung eines binären Haufens implementiert. Die Bibliothek enthüllt eine HeaPlace-Funktion zur Unterstützung der K-Wege-Verschmelzung.
  • Php hat beide max-heap ( Splmaxheap) und Min-heap ( Splminheap) Ab Version 5.3 in der Standard -PHP -Bibliothek.
  • Perl hat Implementierungen von Binär-, Binomial- und Fibonacci -Haufen in der Haufen Verteilung verfügbar auf CPAN.
  • Das gehen Sprache enthält a Haufen Paket mit Heap -Algorithmen, die mit einem willkürlichen Typ arbeiten, der eine bestimmte Schnittstelle erfüllt. Dieses Paket unterstützt nicht die Ersatz-, Sift-up/Sift-Down- oder Verringerung/Erhöhung-Key-Operationen.
  • Äpfel Kernfundament Bibliothek enthält a CFBINYHEAP Struktur.
  • Pharo hat eine Implementierung eines Haufens im Sammlungs-Sequencable-Paket zusammen mit einer Reihe von Testfällen. Bei der Implementierung der Timer -Ereignisschleife wird ein Heap verwendet.
  • Das Rost Die Programmiersprache hat eine binäre Max-heap-Implementierung, Binaryheap, in dem Sammlungen Modul seiner Standardbibliothek.
  • .NETZ hat Prioritätswarteschlange Klasse, die eine viertelnde (D-Ary) Min-H-H-H-Ablehnung verwendet. Es ist bei .net 6 erhältlich.

Siehe auch

Verweise

  1. ^ Cormen, Thomas H. (2009). Einführung in Algorithmen. Vereinigte Staaten von Amerika: The MIT Press Cambridge, Massachusetts London, England. S. 151–152. ISBN 978-0-262-03384-8.
  2. ^ Black (Hrsg.), Paul E. (2004-12-14). Eintrag für Haufen in Wörterbuch von Algorithmen und Datenstrukturen. Online Version. UNS. Nationales Institut für Standards und Technologie, 14. Dezember 2004. Abgerufen am 2017-10-08 von abgerufen https://xlinux.nist.gov/dads/html/heap.html.
  3. ^ Williams, J. W. J. (1964), "Algorithmus 232 - Heapsort", Kommunikation der ACM, 7 (6): 347–348, doi:10.1145/512274.512284
  4. ^ Die Python Standard Library, 8.4. Heapq - Heap -Warteschlangenalgorithmus, heapq.heappush
  5. ^ Die Python Standard Library, 8.4. Heapq - Heap -Warteschlangenalgorithmus, Heapq.Heapop
  6. ^ Die Python Standard Library, 8.4. Heapq - Heap -Warteschlangenalgorithmus, heapq.Heafreplace
  7. ^ Sucheenek, Marek A. (2012), "Elementare, aber präzise Worst-Case-Analyse des HEAP-Construction-Programms von Floyd", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/fi-2012-751.
  8. ^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Einführung in Algorithmen (1. Aufl.). MIT Press und McGraw-Hill. ISBN 0-262-03141-8.
  9. ^ "Binomial Heap | Brilliantes Mathematik & Naturwissenschaft Wiki". Brilliant.org. Abgerufen 2019-09-30.
  10. ^ Fredman, Michael Lawrence; Tarjan, Robert E. (Juli 1987). "Fibonacci Heaps und ihre Verwendung in verbesserten Netzwerkoptimierungsalgorithmen" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. Citeseerx 10.1.1.309.8927. doi:10.1145/28869.28874.
  11. ^ Iacono, John (2000), "Verbesserte Obergrenzen für die Paarung von Haufen", Proc. 7. skandinavischer Workshop zur Algorithmustheorie (PDF), Vorlesungsnotizen in Informatik, Vol. 1851, Springer-Verlag, S. 63–77, Arxiv:1110.4428, Citeseerx 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
  12. ^ Fredman, Michael Lawrence (Juli 1999). "Über die Effizienz von Haufen und verwandten Datenstrukturen" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
  13. ^ Pettie, Seth (2005). Auf eine endgültige Analyse der Paarungshaufen (PDF). FOCS '05 Proceedings des 46. jährlichen IEEE -Symposiums für Fundamente der Informatik. S. 174–183. Citeseerx 10.1.1.549.471. doi:10.1109/sfcs.2005.75. ISBN 0-7695-2468-0.
  14. ^ Brodal, Gerth S. (1996), "Worst-Case Effiziente Prioritätswarteschlangen" (PDF), Proc. 7. jährliches ACM-SIAM-Symposium für diskrete Algorithmen, S. 52–58
  15. ^ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-up Heap Construction". Datenstrukturen und Algorithmen in Java (3. Aufl.). S. 338–341. ISBN 0-471-46983-1.
  16. ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rang-Pairing-Haufen" (PDF). Siam J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
  17. ^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strenge Fibonacci -Haufen (PDF). Verfahren des 44. Symposiums über die Theorie des Computers - STOC '12. S. 1177–1184. Citeseerx 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
  18. ^ Takaoka, Tadao (1999), Theorie von 2–3 Haufen (PDF), p. 12
  19. ^ Frederickson, Greg N. (1993), "Ein optimaler Algorithmus für die Selektion in einem Min-heap", Informationen und Berechnung (PDF), vol. 104, Academic Press, S. 197–214, doi:10.1006/inco.1993.1030, archiviert von das Original (PDF) Am 2012-12-03, abgerufen 2010-10-31

Externe Links

  • Haufen bei Wolfram Mathworld
  • Erläuterung Wie die grundlegenden Heap -Algorithmen funktionieren
  • Bentley, Jon Louis (2000). Programmierperlen programmieren (2. Aufl.). Addison Wesley. S. 147–162. ISBN 0201657880.