Heap (Datenstruktur)

Ein Heap (englisch wörtlich: Haufen oder Halde) in der Informatik ist eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung von Mengen. Den Elementen ist dabei ein Schlüssel zugeordnet, der die Priorität der Elemente festlegt. Häufig werden auch die Elemente selbst als Schlüssel verwendet.

Über die Menge der Schlüssel muss daher eine totale Ordnung festgelegt sein, über welche die Reihenfolge der eingefügten Elemente festgelegt wird. Beispielsweise könnte die Menge der ganzen Zahlen zusammen mit dem Vergleichsoperator < als Schlüsselmenge fungieren.

Der Begriff Heap wird häufig als bedeutungsgleich zu einem partiell geordneten Baum verstanden (siehe Abbildung). Gelegentlich versteht man einschränkend nur eine besondere Implementierungsform eines partiell geordneten Baums, nämlich die Einbettung in ein Array, als Heap.

Verwendung finden Heaps vor allem dort, wo es darauf ankommt, schnell ein Element mit höchster Priorität aus dem Heap zu entnehmen (HIFO-Prinzip), beispielsweise bei Vorrangwarteschlangen.

Operationen

Je nach Art unterstützen Heaps eine ganze Reihe von Operationen. Die wichtigsten Operationen sind

insert: zum Einfügen eines Elementes,
remove: zum Entfernen eines Elementes und
extractMin: zur Rückgabe und dem Entfernen eines Elementes mit minimalem Schlüssel, also höchster Priorität.

Daneben werden häufig auch die Operationen changeKey zum Anpassen des Schlüssels und merge zum Verschmelzen zweier Heaps bereitgestellt. Die Operation changeKey wird häufig durch die Nacheinanderausführung der Operationen remove und insert gebildet, wobei nach dem Entfernen und vor dem erneuten Einfügen der Schlüssel angepasst wird. In einigen Fällen bieten Heaps statt changeKey lediglich die Operation decreaseKey an, bei der der Schlüssel lediglich verkleinert werden darf.

Heap-Bedingung

Man unterscheidet Heaps in Min-Heaps und Max-Heaps. Bei Min-Heaps bezeichnet man die Eigenschaft, dass die Schlüssel der Kinder eines Knotens stets größer oder gleich als der Schlüssel ihres Vaters sind, als Heap-Bedingung. Dies bewirkt, dass an der Wurzel des Baumes stets ein Element mit minimalem Schlüssel im Baum zu finden ist. Umgekehrt verlangt die Heap-Bedingung bei Max-Heaps, dass die Schlüssel der Kinder eines Knotens stets kleiner oder gleich als die ihres Vaters sind. Hier befindet sich an der Wurzel des Baumes immer ein Element mit maximalem Schlüssel.

Mathematisch besteht der Unterschied zwischen beiden Varianten nur in ihrer gegensätzlichen Ordnung der Elemente. Da die Definition von auf- und absteigend rein willkürlich ist, ist es also eine Auslegungsfrage, ob es sich bei einer konkreten Implementierung um einen Min-Heap oder um einen Max-Heap handelt.

Oft kommt es auch vor, dass ein Heap die Heap-Eigenschaft in beiden Richtungen abbilden soll. In diesem Fall werden einfach zwei Heaps geschaffen, wobei der eine nach der Kleiner- und der andere nach der Größer-Relation anordnet. Eine derartige Datenstruktur wird dann Doppelheap oder kurz Deap genannt.

Bei der Verwendung von Doppel-Heaps ist zu beachten, dass nicht jede Implementierung von Heaps dabei ihr Laufzeitverhalten für die einzelnen Operationen behält. Zum Beispiel unterstützen Fibonacci-Heaps nur ein decreaseKey zum Verringern der Schlüssel mit amortisiert konstanter Laufzeit. Ein allgemeineres changeKey zum Ändern des Schlüssels, welches man im Falle eines derartigen Doppel-Heaps benötigen würde, braucht aber amortisiert mindestens logarithmische Laufzeit.

Eine Variante von Heaps, die die Heap-Bedingung nur eingeschränkt bzw. in abgewandelter Form unterstützt, sind sogenannte Min-Max-Heaps. Dabei handelt es sich um Doppel-Heaps, die durch die abgewandelte Form der Heap-Bedingung die Daten in nur einem Baum halten können.

Implementierung

Beispiel eines vollständigen binären Max-Heaps, der in einem Array gespeichert wird.

Heaps werden normalerweise mit einer impliziten Heap-Datenstruktur implementiert, bei der es sich um eine implizite Datenstruktur handelt, die aus einem Array fester Größe oder einem dynamisches Array besteht, wobei jedes Element den Knoten eines Baums darstellt, dessen Vater-Kind-Relation implizit durch seinen Index definiert wird. Nachdem ein Element in einen Heap eingefügt oder aus einem Heap gelöscht wurde, kann die Heap-Eigenschaft verletzt werden und der Heap muss durch Austauschen von Elementen innerhalb des Arrays ausgeglichen werden.

In einer impliziten Heap-Datenstruktur enthält das erste oder letzte Element die Wurzel. Die nächsten beiden Elemente des Arrays enthalten seine untergeordneten Elemente. Die nächsten vier Elemente enthalten die vier Kinder der beiden Kindknoten usw. Somit würden sich die Kinder des Knotens an Position n an den Positionen 2n und 2n + 1 in einem Array mit Startindex 1 oder an den Positionen 2n + 1 und 2n + 2 in in einem Array mit Startindex 0 befinden. Die Berechnung des Index des übergeordneten Knotens des Elements an Position n ist ebenfalls unkompliziert. Bei einem Array mit Startindex 1 befindet sich das übergeordnete Element an Position n / 2. Bei einem Array mit Startindex 0 das übergeordnete Element an der Position (n - 1) / 2. Dies ermöglicht das Durchlaufen des Baums durch einfache Indexberechnungen. Das Ausbalancieren eines Heaps erfolgt durch Austauschen von Elementen, die nicht in Ordnung sind. Da wir einen Heap aus einem Array erstellen können, ohne zusätzlichen Speicher zu benötigen, kann Heapsort verwendet werden, um ein Array in-place zu sortieren.

Verschiedene Arten von Heaps implementieren die Operationen auf unterschiedliche Weise. Insbesondere erfolgt das Einfügen jedoch häufig durch Hinzufügen des neuen Elements am Ende des Heaps im ersten verfügbaren freien Platz. Dies verstößt im Allgemeinen gegen die Heap-Eigenschaft. Daher werden die Elemente nach oben verschoben, bis die Heap-Eigenschaft wiederhergestellt wurde. In ähnlicher Weise wird das Löschen der Wurzel durchgeführt, indem die Wurzel entfernt und dann das letzte Element in die Wurzel eingefügt und zum Ausgleich gesiebt wird. Das Ersetzen erfolgt also durch Löschen der Wurzel und Einfügen des neuen Elements in die Wurzel und Durchsieben, wobei ein Aufwärtsschritt im Vergleich zum Absenken des letzten Elements gefolgt vom Aufsteigen des neuen Elements vermieden wird.

Varianten von Heaps

Es existieren zahlreiche Arten von Heaps mit unterschiedlich gutem Laufzeitverhalten für die verschiedenen Operationen, die sie zur Verfügung stellen. Beispiele für Heaps sind:

Außerdem gibt es mit Soft Heaps eine Variante bei der ein besseres Laufzeitverhalten erreicht wird, indem ein bestimmter Anteil der Schlüssel verdorben werden kann. Diese verdorbenen Schlüssel haben nicht mehr ihren ursprünglichen Wert.

Laufzeitverhalten

Die folgende Tabelle gibt die Laufzeiten von verschiedenen Heaps bezüglich ihrer Operationen an.

Operation	Binärer Heap	Binomial Heap	Fibonacci Heap	Pairing	Leftist	2-3-Heap
Operation			amortisiert	amortisiert	amortisiert
extract-min	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$
remove	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$
insert	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(1)$	${\mathcal {O}}(\log n)$ ( ${\mathcal {O}}(1)$ vermutet)	${\mathcal {O}}(1)$ oder ${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$
decrease-key	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(1)$	${\mathcal {O}}(\log n)$ ( ${\mathcal {O}}(1)$ vermutet)	${\mathcal {O}}(1)$ oder ${\mathcal {O}}(\log n)$	${\mathcal {O}}(1)$
merge	${\mathcal {O}}(n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(1)$	${\mathcal {O}}(\log n)$ ( ${\mathcal {O}}(1)$ vermutet)	${\mathcal {O}}(1)$ oder ${\mathcal {O}}(\log n)$

Anwendung

Heaps haben ein breites Spektrum an Anwendungen. Häufig ist vor allem der Einsatz in Vorrangwarteschlangen, wie sie bei Servern oder Betriebssystemen zur Festlegung der Ausführungsreihenfolge von Aufgaben benötigt werden.

Daneben gibt es aber auch Anwendungen, die nicht explizit den Einsatz von Warteschlangen verlangen. Allgemein stellt ein Heap eine ideale Datenstruktur für Greedy-Algorithmen dar, die schrittweise lokale optimierte Entscheidungen treffen. So wird zum Beispiel beim Sortieralgorithmus Heapsort ein Binärer Heap zum Sortieren eingesetzt. Fibonacci-Heaps finden beim Algorithmus von Dijkstra bzw. Prim Anwendung.

Siehe auch

Literatur

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 127 (englisch).
Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 144–155 (englisch).

Weblinks

Commons: Heaps – Sammlung von Bildern, Videos und Audiodateien