Heap (Datenstruktur) - Heap (data structure)

Beispiel für einen binären Max-Heap mit Knotenschlüsseln, die ganze Zahlen zwischen 1 und 100 . sind

In der Informatik , ein Haufen ist eine spezialisierter Baum -basierte Datenstruktur , die im wesentlichen ein fast vollständiger Baum ist , dass die erfüllt Heapeigenschaft : in einem max heap , für jeden gegebenen Knoten C, wenn P ein Elternknoten von C, dann wird der Schlüssel (der Wert ) von P ist größer oder gleich dem Schlüssel von C. In einem min heap ist der Schlüssel von P kleiner oder gleich dem Schlüssel von C. Der Knoten an der "Spitze" des Heaps (mit no Eltern) wird als Wurzelknoten bezeichnet .

Der Heap ist eine maximal effiziente Implementierung eines abstrakten Datentyps, der als Prioritätswarteschlange bezeichnet wird , und tatsächlich werden Prioritätswarteschlangen oft als "Heaps" bezeichnet, unabhängig davon, wie sie implementiert werden können. In einem Heap wird das Element mit der höchsten (oder niedrigsten) Priorität immer an der Wurzel gespeichert. Ein Heap ist jedoch keine sortierte Struktur; sie kann als teilweise geordnet angesehen werden. Ein Heap ist eine nützliche Datenstruktur, wenn das Objekt mit der höchsten (oder niedrigsten) Priorität wiederholt entfernt werden muss.

Eine gängige Implementierung eines Heaps ist der Binary Heap , bei dem der Baum ein Binärbaum ist (siehe Abbildung). Die Heap-Datenstruktur, insbesondere der binäre Heap, wurde 1964 von JWJ Williams als Datenstruktur für den Heapsort- Sortieralgorithmus eingeführt. Heaps sind auch in mehreren effizienten Graphalgorithmen wie dem Algorithmus von Dijkstra von entscheidender Bedeutung . Wenn eine Halde ein vollständiger binärer Baum ist, hat es eine möglichst geringe Höhe eine Halde mit N Knoten und für jeden Knoten ein Zweige hat immer log _eine N Höhe.

Beachten Sie, dass es, wie in der Grafik gezeigt, keine implizite Reihenfolge zwischen Geschwistern oder Cousins ​​und keine implizite Sequenz für eine Durchquerung in der Reihenfolge gibt (wie dies zB in einem binären Suchbaum der Fall wäre ). Die oben erwähnte Heap-Beziehung gilt nur zwischen Knoten und ihren Eltern, Großeltern usw. Die maximale Anzahl von Kindern, die jeder Knoten haben kann, hängt vom Typ des Heaps ab.

Betrieb

Die üblichen Operationen mit Haufen sind:

Basic

• find-max (oder find-min ): Finde ein maximales Element eines Max-Heaps bzw. ein minimales Element eines Min-Heaps (auch bekannt als peek )
• Einfügen : Hinzufügen eines neuen Schlüssels zum Heap (auch bekannt als Push )
• extrahieren-max (oder extrahieren-min ): gibt den Knoten mit dem maximalen Wert aus einem maximalen Heap [oder minimalen Wert aus einem min-Heap] zurück, nachdem er aus dem Heap entfernt wurde (auch bekannt als pop )
• delete-max (oder delete-min ): Entfernen des Wurzelknotens eines Max-Heaps (bzw. Min-Heaps)
• Ersetzen : Pop-Root und drücken Sie eine neue Taste. Effizienter als Pop gefolgt von Push, da nur einmal und nicht zweimal balanciert werden muss und für Heaps mit fester Größe geeignet ist.

Schaffung

• create-heap : einen leeren Haufen erstellen
• heapify : Erzeuge einen Heap aus einem gegebenen Array von Elementen
• merge ( union ): Zusammenführen von zwei Heaps, um einen gültigen neuen Heap zu bilden, der alle Elemente von beiden enthält, wobei die ursprünglichen Heaps erhalten bleiben.
• meld : Zusammenfügen zweier Heaps zu einem gültigen neuen Heap, der alle Elemente von beiden enthält, wobei die ursprünglichen Heaps zerstört werden.

Inspektion

• size : Gibt die Anzahl der Elemente im Heap zurück.
• is-empty : Gibt true zurück, wenn der Heap leer ist, andernfalls false.

Intern

• Erhöhen-Taste oder Verkleinern-Taste : Aktualisieren eines Schlüssels innerhalb eines Max- bzw. Min-Heaps
• delete : Löschen eines beliebigen Knotens (gefolgt vom Verschieben des letzten Knotens und Sieben, um den Heap zu erhalten)
• sift-up : Verschieben Sie einen Knoten im Baum nach oben, so lange wie nötig; Wird verwendet, um den Heap-Zustand nach dem Einfügen wiederherzustellen. Wird als "Sift" bezeichnet, weil der Knoten den Baum nach oben bewegt, bis er die richtige Ebene erreicht, wie in einem Sieb .
• sift-down : Verschiebt einen Knoten im Baum nach unten, ähnlich wie bei sift-up; Wird verwendet, um den Heap-Zustand nach dem Löschen oder Ersetzen wiederherzustellen.

Implementierung

Heaps werden normalerweise wie folgt mit einem Array implementiert :

• Jedes Element im Array repräsentiert einen Knoten des Heaps, und
• Die Eltern-Kind-Beziehung wird implizit durch die Indizes der Elemente im Array definiert.

Beispiel für einen vollständigen binären Max-Heap mit Knotenschlüsseln, die ganze Zahlen von 1 bis 100 sind, und wie er in einem Array gespeichert würde.

Bei einem binären Heap enthält der erste Index im Array das Wurzelelement. Die nächsten beiden Indizes des Arrays enthalten die Kinder der Wurzel. Die nächsten vier Indizes enthalten die vier Kinder der beiden untergeordneten Knoten der Wurzel usw. Daher sind bei einem gegebenen Knoten am Index i seine Kinder an den Indizes 2i + 1 und 2i + 2 und sein Elternknoten am Index ⌊(i−1)/2⌋ . Dieses einfache Indexierungsschema macht es effizient, sich im Baum "nach oben" oder "nach unten" zu bewegen.

Das Ausbalancieren eines Haufens erfolgt durch Sift-Up- oder Sift-Down-Operationen (Austausch von Elementen, die nicht in Ordnung sind). Da wir einen Heap aus einem Array erstellen können, ohne zusätzlichen Speicher (zum Beispiel für die Knoten) zu benötigen, kann Heapsort verwendet werden, um ein Array direkt zu sortieren.

Nachdem ein Element in einen Heap eingefügt oder daraus gelöscht wurde, kann die Heap-Eigenschaft verletzt werden, und der Heap muss durch Austauschen von Elementen innerhalb des Arrays neu ausgeglichen werden.

Obwohl verschiedene Heap- Typen die Operationen unterschiedlich implementieren, ist die gängigste Methode wie folgt:
Einfügen: Fügen Sie das neue Element am Ende des Heaps im ersten verfügbaren freien Speicherplatz hinzu. Dadurch wird die Heap-Eigenschaft verletzt, sodass die Elemente nach oben verschoben werden (oder der Schwimmvorgang ausgeführt wird), bis die Heap-Eigenschaft wiederhergestellt wurde.
Extraktion: die Wurzel entfernen und das letzte Element des Haufens in der Wurzel einzufügen und dies wird die Heapeigenschaft verletzt, so, sichten Sie den Heap - Eigenschaft (oder wiederherzustellen sink Betrieb). Das Ersetzen erfolgt also durch Löschen der Wurzel und Einfügen des neuen Elements in die Wurzel und Absieben, wodurch ein Aufwärtssieben im Vergleich zu pop (Abwärtssieben des letzten Elements) gefolgt von Push (Aufwärtssieben eines neuen Elements) vermieden wird.

Die Konstruktion eines binären (oder d- ären) Heaps aus einem gegebenen Array von Elementen kann in linearer Zeit unter Verwendung des klassischen Floyd-Algorithmus durchgeführt werden , wobei die ungünstigste Anzahl von Vergleichen gleich 2 N − 2 s ₂ ( N ) − . ist e ₂ ( N ) (für einen binären Haufen), wobei s ₂ ( N ) die Summe aller Ziffern der binären Darstellung von N ist und e ₂ ( N ) der Exponent von 2 bei der Primfaktorzerlegung von N ist . Dies ist schneller als eine Folge aufeinander folgender Einfügungen in einen ursprünglich leeren Heap, der log-linear ist.

Varianten

Vergleich der theoretischen Schranken für Varianten

Hier sind die zeitlichen Komplexitäten verschiedener Heap-Datenstrukturen. Funktionsnamen gehen von einem Max-Heap aus. Zur Bedeutung von „ O ( f )“ und „ Θ ( f )“ siehe Big O-Notation .

Anwendungen

Die Heap-Datenstruktur hat viele Anwendungen.

• Heapsort : Eine der besten Sortiermethoden, die vorhanden ist und keine quadratischen Worst-Case-Szenarien aufweist.
• Auswahlalgorithmen : Ein Heap ermöglicht den Zugriff auf das min- oder max-Element in konstanter Zeit, und andere Auswahlen (wie Median- oder k-te-Elemente) können in sublinearer Zeit für Daten, die sich in einem Heap befinden, durchgeführt werden.
• Graphalgorithmen : Durch die Verwendung von Heaps als interne Traversierungsdatenstrukturen wird die Laufzeit um polynomielle Ordnung reduziert. Beispiele für solche Probleme sind der Minimal-Spanning-Tree-Algorithmus von Prim und der Shortest-Path-Algorithmus von Dijkstra .
• Prioritätswarteschlange : Eine Prioritätswarteschlange 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 Prioritätswarteschlange mit einem Heap oder einer Vielzahl anderer Methoden implementiert werden.
• K-Weg-Merge : Eine Heap-Datenstruktur ist nützlich, um viele bereits sortierte Eingabeströme zu einem einzigen sortierten Ausgabestrom zusammenzuführen. Beispiele für die Notwendigkeit einer Zusammenführung umfassen externe Sortier- und Streaming-Ergebnisse von verteilten Daten, wie beispielsweise ein protokollstrukturierter Zusammenführungsbaum. Die innere Schleife ruft das min-Element ab, ersetzt es durch das nächste Element für den entsprechenden Eingabestrom und führt dann eine Heap-Sichtoperation aus. (Alternativ die Ersetzungsfunktion.) (Die Verwendung von Extract-Max- und Insert-Funktionen einer Prioritätswarteschlange ist viel weniger effizient.)
• Ordnungsstatistik : Die Heap-Datenstruktur kann verwendet werden, um das k-kleinste (oder größte) Element in einem Array effizient zu finden.

Programmiersprachenimplementierungen

• Die C++-Standardbibliothek stellt die Algorithmen make_heap , push_heap und pop_heap für Heaps (normalerweise als binäre Heaps implementiert) bereit , die auf beliebigen Iteratoren mit wahlfreiem Zugriff arbeiten . Es behandelt die Iteratoren als Verweis auf ein Array und verwendet die Array-in-Heap-Konvertierung. Es stellt auch den Containeradapter Priority_queue bereit , der diese Einrichtungen in eine containerähnliche Klasse einschließt. Es gibt jedoch keine Standardunterstützung für die Ersetzungs-, Aufwärts-/Abwärts- oder Verkleinerungs-/Erhöhungs-Tastenoperationen.
• Die Boost C++-Bibliotheken enthalten eine Heaps-Bibliothek. Im Gegensatz zur STL unterstützt es Verkleinerungs- und Vergrößerungsoperationen und unterstützt zusätzliche Arten von Heaps: insbesondere unterstützt es D- Ary-, Binomial-, Fibonacci-, Pairing- und Skew-Heaps.
• Es gibt eine generische Heap-Implementierung für C und C++ mit D-ary-Heap- und B-Heap- Unterstützung. Es bietet eine STL-ähnliche API.
• Die Standardbibliothek der Programmiersprache D enthält std.container.BinaryHeap , die in Bezug auf die Bereiche von D implementiert ist . Instanzen können aus einem beliebigen Direktzugriffsbereich erstellt werden . BinaryHeap stellt eine Eingabebereichsschnittstelle bereit , die eine Iteration mit den integrierten foreach- Anweisungen von D und die Integration mit der bereichsbasierten API des std.algorithm- Pakets ermöglicht .
• Die Java- Plattform (seit Version 1.5) stellt eine binäre Heap-Implementierung mit der Klasse java.util.PriorityQueueim Java Collections Framework bereit . 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 die Ersetzungs-, Aufwärts-/Abwärts- oder Verkleinerungs-/Erhöhungs-Tastenoperationen.
• Python hat ein heapq- Modul, das eine Prioritätswarteschlange mithilfe eines binären Heaps implementiert. Die Bibliothek stellt eine Heapreplace-Funktion bereit, um die K-Wege-Zusammenführung zu unterstützen.
• PHP hat ab Version 5.3 sowohl Max-Heap ( SplMaxHeap ) als auch Min-Heap ( SplMinHeap ) in der Standard PHP Library.
• Perl hat Implementierungen von Binär-, Binomial- und Fibonacci-Heaps in der auf CPAN verfügbaren Heap- Distribution .
• Die Sprache Go enthält ein Heap- Paket mit Heap-Algorithmen, die auf einem beliebigen Typ arbeiten, der eine gegebene Schnittstelle erfüllt. Dieses Paket unterstützt nicht die Ersetzungs-, Aufwärts-/Abwärts- oder Verkleinerungs-/Erhöhungs-Tastenoperationen.
• Die Core Foundation- Bibliothek von Apple enthält eine CFBinaryHeap- Struktur.
• Pharo hat eine Implementierung eines Heaps im Collections-Sequenceable-Paket zusammen mit einer Reihe von Testfällen. Bei der Implementierung der Timer-Ereignisschleife wird ein Heap verwendet.
• Die Programmiersprache Rust hat eine binäre Max-Heap-Implementierung, BinaryHeap , im Collections- Modul ihrer Standardbibliothek.

Siehe auch

• Sortieralgorithmus
• Datenstruktur suchen
• Stack (abstrakter Datentyp)
• Warteschlange (abstrakter Datentyp)
• Baum (Datenstruktur)
• Treap , eine Form eines binären Suchbaums basierend auf heap -geordneten Bäumen

Verweise

Externe Links

• Haufen bei Wolfram MathWorld
• Erläuterung der Funktionsweise der grundlegenden Heap-Algorithmen
• Bentley, Jon Louis (2000). Programmierperlen (2. Aufl.). Addison Wesley. S. 147–162. ISBN 0201657880.