Heap (Datenstruktur)

Grundidee und Zweck

Ein Heap ist in der Informatik eine abstrakte Datenstruktur, die meist auf Bäumen basiert. In einem Heap können Elemente gespeichert und wieder entnommen werden. Jedem Element ist ein Schlüssel zugeordnet, der seine Priorität festlegt; oft wird das Element selbst als Schlüssel verwendet. Über der Schlüsselmenge muss eine totale Ordnung festgelegt sein, damit Elemente vergleichbar sind, zum Beispiel die ganzen Zahlen mit dem Vergleichsoperator <.

Heaps werden besonders dann verwendet, wenn schnell ein Element mit höchster Priorität entnommen werden soll. Dieses Prinzip heißt HIFO-Prinzip. Ein typisches Einsatzgebiet sind Vorrangwarteschlangen, bei denen nicht das zuerst eingefügte, sondern das wichtigste Element zuerst verarbeitet wird.

Der Begriff Heap wird häufig als partiell geordneter Baum verstanden. Manchmal bezeichnet er enger eine bestimmte Implementierung eines solchen Baums in einem Feld, also einem Array.

Heap-Bedingung

Die Heap-Bedingung legt fest, wie Elternknoten und Kindknoten im Baum geordnet sein müssen. Man unterscheidet Min-Heaps und Max-Heaps.

Bei einem Min-Heap sind die Schlüssel der Kinder eines Knotens immer größer als oder gleich dem Schlüssel ihres Elternknotens. Dadurch steht an der Wurzel des Baumes immer ein Element mit minimalem Schlüssel.

Bei einem Max-Heap sind die Schlüssel der Kinder eines Knotens immer kleiner als oder gleich dem Schlüssel ihres Elternknotens. Dadurch steht an der Wurzel immer ein Element mit maximalem Schlüssel.

Mathematisch unterscheiden sich Min-Heap und Max-Heap nur durch die entgegengesetzte Ordnung der Elemente. Da die Definition von aufsteigend und absteigend willkürlich ist, hängt es von der Auslegung ab, ob eine konkrete Implementierung als Min-Heap oder Max-Heap betrachtet wird.

Wenn ein Heap die Heap-Eigenschaft in beide Richtungen abbilden soll, können zwei Heaps verwendet werden: einer nach der Kleiner-Relation und einer nach der Größer-Relation. Eine solche Datenstruktur heißt Doppelheap oder Deap. Dabei behalten aber nicht alle Heap-Implementierungen ihr Laufzeitverhalten. Fibonacci-Heaps unterstützen zum Beispiel decreaseKey, also das Verringern eines Schlüssels, mit amortisiert konstanter Laufzeit. Ein allgemeineres changeKey zum Ändern eines Schlüssels braucht in einem solchen Fall amortisiert mindestens logarithmische Laufzeit.

Min-Max-Heaps sind eine Variante von Doppel-Heaps. Sie halten die Daten durch eine abgewandelte Heap-Bedingung in nur einem Baum.

Wichtige Operationen

Heapify ordnet die Elemente eines Heaps neu an, damit die Heap-Bedingung wieder gilt. Sie wird verwendet, wenn ein Knoten ein Ungleichgewicht verursacht. Bei Up-Heapify wird von unten nach oben in Richtung der Wurzel geprüft und korrigiert. Bei Down-Heapify wird von oben nach unten in Richtung der Blätter geprüft und korrigiert.

Insert fügt ein neues Element ein. Das neue Element wird zunächst an das Ende des Heaps gesetzt. Weil dadurch die Heap-Eigenschaft verletzt sein kann, wird anschließend Up-Heapify ausgeführt.

Remove entfernt ein Element. Das gelöschte Element wird durch das letzte Element im Heap ersetzt, danach wird dieses letzte Element aus dem Heap gelöscht. Da das ersetzende Element an seiner neuen Stelle die Heap-Bedingung verletzen kann, wird Down-Heapify ausgeführt.

Find-max oder Find-min liefert das maximale Element im Max-Heap beziehungsweise das minimale Element im Min-Heap. Dieses Element befindet sich jeweils an der Wurzel.

Extract Min oder Extract Max gibt das minimale Element im Min-Heap oder das maximale Element im Max-Heap zurück. Auch dieses Element ist die Wurzel des Heaps.

Zusätzlich bieten viele Heaps changeKey zum Ändern eines Schlüssels und merge zum Verschmelzen zweier Heaps. changeKey kann durch remove und insert gebildet werden: Zuerst wird das Element entfernt, dann wird der Schlüssel angepasst, danach wird es wieder eingefügt. Manche Heaps bieten statt changeKey nur decreaseKey an, wobei der Schlüssel nur verkleinert werden darf.

Implementierung im Array

Heaps werden normalerweise mit einer impliziten Heap-Datenstruktur implementiert. Dabei liegt der Baum in einem Feld fester Größe oder in einem dynamischen Array. Jedes Array-Element stellt einen Knoten dar; die Eltern-Kind-Beziehung wird nicht durch Zeiger, sondern durch den Index berechnet.

In einem solchen Array enthält das erste oder letzte Element die Wurzel. Die nächsten zwei Elemente enthalten die Kinder der Wurzel, die nächsten vier Elemente die Kinder dieser beiden Kindknoten und so weiter. Bei einem Array mit Startindex 1 liegen die Kinder des Knotens an Position n an den Positionen 2n und 2n + 1; der Elternknoten liegt an Position n / 2. Bei einem Array mit Startindex 0 liegen die Kinder an den Positionen 2n + 1 und 2n + 2; der Elternknoten liegt an Position (n - 1) / 2.

Diese Darstellung ermöglicht es, den Baum mit einfachen Indexberechnungen zu durchlaufen. Das Ausbalancieren geschieht durch Vertauschen von Elementen, die nicht in Ordnung sind. Weil ein Heap aus einem Array ohne zusätzlichen Speicher erstellt werden kann, kann Heapsort ein Array in-place sortieren.

Beim Einfügen wird ein neues Element häufig am Ende des Heaps in den ersten freien Platz gesetzt und anschließend nach oben verschoben, bis die Heap-Eigenschaft wieder gilt. Beim Löschen der Wurzel wird die Wurzel entfernt, das letzte Element an die Wurzel gesetzt und dann nach unten gesiebt.

Varianten und Laufzeiten

Ein binärer Heap kann mit linearem Zeitaufwand in O(n) konstruiert werden, wobei n die Anzahl der Elemente aus der Eingabe bezeichnet. Die Operationen insert, remove, extractMin und decreaseKey haben im Worst Case jeweils eine Laufzeit von O(log n). getMin liefert das kleinste Element mit konstantem Rechenaufwand.

Binomial-Heaps unterstützen insert, remove, extractMin, changeKey und merge. Alle diese Operationen lassen sich mit einer Worst-Case-Laufzeit von O(log n) implementieren, wobei n die Zahl der Elemente im Heap ist.

Ein Fibonacci-Heap ist ähnlich wie ein Binomial-Heap in einer Vorrangwarteschlange realisiert: Elemente mit Prioritäten können effizient gespeichert werden, und ein Element mit höchster Priorität kann entnommen werden. Für Fibonacci-Heaps nennt die Laufzeittabelle amortisiert O(log n) für extract-min und remove sowie amortisiert O(1) für insert, decrease-key und merge.

Weitere Varianten sind Min-Max-Heap, Linksbaum, Treap, Radix-Heap, Pairing-Heap, 2-3-Heap und Soft Heap. Bei Soft Heaps wird ein besseres Laufzeitverhalten dadurch erreicht, dass ein bestimmter Anteil der Schlüssel verdorben werden kann; diese Schlüssel haben dann nicht mehr ihren ursprünglichen Wert.

Die Laufzeittabelle nennt unter anderem für Pairing-Heaps amortisiert O(log n) für extract-min, remove, insert, decrease-key und merge, wobei für insert, decrease-key und merge O(1) vermutet wird. Für Linksbäume wird bei insert, decrease-key und merge O(1) oder O(log n) angegeben. Für 2-3-Heaps stehen O(log n) für extract-min, remove und insert sowie O(1) für decrease-key.

Anwendungen

Heaps werden in vielen Bereichen eingesetzt. Besonders häufig verwendet man sie für Vorrangwarteschlangen, zum Beispiel bei Servern oder Betriebssystemen, wenn die Ausführungsreihenfolge von Aufgaben festgelegt werden muss.

Außerdem eignen sich Heaps für Greedy-Algorithmen. Greedy-Algorithmen treffen schrittweise lokal optimierte Entscheidungen. Der Sortieralgorithmus Heapsort verwendet zum Beispiel einen binären Heap zum Sortieren. Fibonacci-Heaps werden beim Algorithmus von Dijkstra und beim Algorithmus von Prim eingesetzt.