In der Informatik ist ein Haufen eine baumbasierte Spezialdatenstruktur, die das Haufen-Eigentum befriedigt: Wenn B ein Kinderknoten von A, dann Schlüssel (A)  Schlüssel (B) ist. Das deutet an, dass ein Element mit dem größten Schlüssel immer im Wurzelknoten ist, und so wird solch ein Haufen manchmal einen Max-Haufen genannt. (Wechselweise, wenn der Vergleich umgekehrt wird, ist das kleinste Element immer im Wurzelknoten, der auf einen Minute-Haufen hinausläuft.) Hängt die maximale Zahl von Kindern, die jeder Knoten haben kann, vom Typ des Haufens ab, aber in vielen Typen ist es höchstens zwei. Der Haufen ist eine maximal effiziente Durchführung eines abstrakten Datentyps genannt eine Vorzugswarteschlange. Haufen sind in mehreren effizienten Graph-Algorithmen wie der Algorithmus von Dijkstra, und im Sortieren-Algorithmus heapsort entscheidend.

Eine Haufen-Datenstruktur sollte mit dem Haufen nicht verwirrt sein, der eine gemeinsame Bezeichnung für das dynamisch zugeteilte Gedächtnis ist. Der Begriff wurde nur für die Datenstruktur ursprünglich gebraucht. Einige frühe populäre Sprachen wie Lispeln haben dynamische Speicherzuteilung mit Haufen-Datenstrukturen zur Verfügung gestellt, die dem Speicherbereich seinen Namen gegeben haben.

Durchführung und Operationen

Haufen werden gewöhnlich in einer Reihe durchgeführt, und verlangen Zeigestöcke zwischen Elementen nicht.

Die mit einem Haufen allgemein durchgeführten Operationen sind:

• Schaffen-Haufen: Schaffen Sie einen leeren Haufen
• finden Sie-max oder finden Sie minutig: Finden Sie den maximalen Artikel eines Max-Haufens oder einen minimalen Artikel eines Minute-Haufens, beziehungsweise
• löschen Sie-max oder löschen Sie minutig: das Entfernen des Wurzelknotens eines max - oder Minute-Haufens, beziehungsweise
• Zunahme-Schlüssel oder Abnahme-Schlüssel: das Aktualisieren eines Schlüssels innerhalb eines max - oder Minute-Haufens, beziehungsweise
• Einsatz: das Hinzufügen eines neuen Schlüssels zum Haufen
• Verflechtung: Das Verbinden zwei Haufen, um einen gültigen neuen Haufen zu bilden, der alle Elemente von beiden enthält.

Verschiedene Typen von Haufen führen die Operationen unterschiedlich durch, aber namentlich wird Einfügung häufig durch das Hinzufügen des neuen Elements am Ende des Haufens im ersten verfügbaren freien Raum getan. Das wird dazu neigen, das Haufen-Eigentum zu verletzen, und so werden die Elemente dann wiederbestellt, bis das Haufen-Eigentum wieder hergestellt worden ist.

Varianten

• 2-3 Haufen
• Beap
• Binärer Haufen
• Binomischer Haufen
• Warteschlange von Brodal
• D-ary Haufen
• Haufen von Fibonacci
• Linksgerichteter Haufen
• Paarung des Haufens
• Verdrehen Sie Haufen
• Weicher Haufen
• Blatt-Haufen
• Basis-Haufen
• Haufen von Randomized meldable

Vergleich von theoretischen Grenzen für Varianten

Das folgende Mal werden Kompliziertheiten (schlecht-malige) Zeitkompliziertheit für Einträge amortisiert, die durch ein Sternchen und regelmäßige Grenzfall-Zeitkompliziertheiten für alle anderen Einträge gekennzeichnet sind. O gibt (f) asymptotisch ober gebunden, und Θ ist (f) gebunden asymptotisch dicht (sieh Große O Notation). Funktionsnamen nehmen einen Minute-Haufen an.

(*) Amortisierte Zeit

(**), Wo n die Größe des größeren Haufens ist

Haufen mit n Elementen können von unten nach oben in O (n) gebaut werden.

Anwendungen

Die Haufen-Datenstruktur hat viele Anwendungen.

• Heapsort: Eine der besten Sortieren-Methoden, die im Platz sind und ohne quadratische größte anzunehmende Unfälle.
• Auswahl-Algorithmen: Die Minute, max, sowohl die Minute als auch max, Mittellinie findend, oder kann sogar das k-th größte Element in der geradlinigen Zeit (häufig unveränderliche Zeit) das Verwenden von Haufen getan werden.
• Graph-Algorithmen: Durch das Verwenden von Haufen als innere überquerende Datenstrukturen wird Durchlaufzeit durch die polynomische Ordnung reduziert. Beispiele solcher Probleme sind der minimale Überspannen-Baumalgorithmus von Prim und das kürzeste Pfad-Problem von Dijkstra.

Volle und fast volle binäre Haufen können in einer sehr raumeffizienten Weise vertreten werden, eine Reihe allein zu verwenden. Das erste (oder letzt) Element wird die Wurzel enthalten. Die folgenden zwei Elemente der Reihe enthalten seine Kinder. Die folgenden vier enthalten die vier Kinder der zwei Kinderknoten usw. So würden die Kinder des Knotens an der Position an Positionen und in einer einer-basierten Reihe, oder und in einer Reihe bei Nullpunkteinstellung sein. Das erlaubt zu steigen oder unten der Baum durch das Tun einfacher Index-Berechnung. Das Ausgleichen eines Haufens wird durch das Tauschen von Elementen getan, die in Unordnung sind. Da wir einen Haufen von einer Reihe bauen können ohne zu verlangen, dass Extragedächtnis (für die Knoten, zum Beispiel), heapsort verwendet werden kann, um eine Reihe im Platz zu sortieren.

Durchführungen

• Der C ++ stellt Standardschablone-Bibliothek den make_heap, push_heap und pop_heap Algorithmen für Haufen zur Verfügung (gewöhnlich durchgeführt als binäre Haufen), die auf dem willkürlichen zufälligen Zugang iterators funktionieren. Es behandelt den iterators als eine Verweisung auf eine Reihe, und verwendet die Konvertierung der Reihe zum Haufen. Behälteradapter priority_queue besteht auch. Jedoch gibt es keine Standardunterstützung für die decrease/increase-key Operation. Siehe auch gheap - STL ähnliche verallgemeinerte Haufen-Durchführung in C ++ mit der D-Haufen- und B-Haufen-Unterstützung.
• Java 2 Plattform (seit der Version 1.5) versorgt die binäre Haufen-Durchführung mit der Klasse java.util. PriorityQueue
• Pythonschlange hat ein heapq Modul, das eine Vorzugswarteschlange durchführt, die einen binären Haufen verwendet.
• PHP hat sowohl maxheap (SplMaxHeap) als auch minheap (SplMinHeap) bezüglich der Version 5.3 in der PHP Standardbibliothek.
• Perl hat Durchführungen von binären, binomischen, und Haufen von Fibonacci im auf CPAN verfügbaren Haufen-Vertrieb.
• Die Gehen Bibliothek enthält ein Haufen-Paket mit Haufen-Algorithmen, die auf einem willkürlichen Typ funktionieren, der eine gegebene Schnittstelle befriedigt hat.
• Die Kernfundament-Bibliothek des Apfels enthält eine Struktur von CFBinaryHeap.

Siehe auch

• Das Sortieren des Algorithmus
• Stapel (Datenstruktur)
• Warteschlange (Datenstruktur)
• Baum (Datenstruktur)
• Treap, eine Form des binären Suchbaums, der auf geordneten Bäumen des Haufens gestützt ist

Links

• Haufen am Wolfram MathWorld