Binärer Heap

Grundidee und Definition

Ein binärer Heap ist eine Datenstruktur der Informatik zum effizienten Sortieren von Elementen. Das asymptotisch optimale Sortierverfahren Heapsort verwendet ihn als zentrale Datenstruktur. Außerdem dient ein binärer Heap zur Implementierung einer Vorrangwarteschlange: Das Element mit der höchsten Priorität kann effizient abgefragt und entfernt werden. Die Priorität wird durch Schlüssel beschrieben; über der Menge dieser Schlüssel muss eine totale Ordnung bestehen, beispielsweise die Kleiner-Relation (<) über den ganzen Zahlen.

Bei Verwendung der Relation < heißt der Heap Min-Heap, bei Verwendung von > Max-Heap. Die Operationen unterscheiden sich nur durch die verwendete Ordnungsrelation. Im Min-Heap gilt für jeden Knoten i außer der Wurzel:

key(H,i) ≥ key(H,parent(i))

Dabei bezeichnet parent(i) den Elternknoten von i. Diese Bedingung heißt Heap-Eigenschaft. Ein Min-Heap ist somit ein partiell geordneter Baum: Eltern- und Kindknoten sind geordnet, die Kinder eines Knotens aber nicht untereinander. Daher befindet sich das kleinste Element an der Wurzel.

Aufbau und Speicherung

Ein binärer Heap ist ein Binärbaum, dessen Ebenen bis auf die letzte vollständig gefüllt sind. Die letzte Ebene wird linksbündig aufgefüllt. Dadurch ist der Baum balanciert. Zusätzlich muss an jedem Knoten die Heap-Eigenschaft gelten: Im Min-Heap ist der Schlüssel jedes Kindes größer oder gleich dem Schlüssel seines Elternknotens.

Häufig wird der Baum nicht mit Zeigern, sondern implizit in einem Array gespeichert. Die Wurzel steht an der ersten Array-Position. Bei einer Indizierung ab 1 stehen die Kinder des Knotens an Position i an den Positionen 2i und 2i+1. Beginnt die Indizierung bei 0, befinden sie sich an den Positionen 2i+1 und 2i+2. Aus diesen Formeln lassen sich auch die Eltern- und Kinderpositionen berechnen. Die Analyse bezeichnet die Heapgröße beziehungsweise die Anzahl der Elemente im Array mit n.

Heapify und Aufbau

Die Funktion heapify stellt die Heap-Eigenschaft eines Teilbaums wieder her, wenn die linken und rechten Teilbäume diese Eigenschaft bereits erfüllen. Sie vergleicht einen Knoten mit seinen Kindern, wählt im Min-Heap das kleinste der drei Elemente und vertauscht es gegebenenfalls mit dem Knoten. Danach wird der Vorgang rekursiv mit der neuen Position fortgesetzt. Der Knoten sinkt dabei so weit nach unten, bis die Heap-Eigenschaft wieder gilt. Dieses Verfahren heißt auch sift-down oder Sift-Down-Phase.

heapify durchläuft höchstens einen Pfad bis zur Tiefe des Baumes und benötigt daher O(height(H)); wegen der logarithmischen Baumhöhe beträgt die Worst-Case-Laufzeit O(log n). Die rekursive Variante benötigt nur eine konstante Anzahl zusätzlicher Speicherzellen, da sie tail-rekursiv ist. Sie kann auch durch eine Schleife ohne Stack ersetzt werden.

Die Funktion build konstruiert aus einem Array einen Heap. Sie beginnt bei den Blättern, die die Heap-Eigenschaft bereits erfüllen, und ruft heapify anschließend bottom-up bis zur Wurzel auf. Bei Array-Indizierung ab 0 beginnt die Iteration bei Position n/2−1 und läuft rückwärts. Obwohl heapify O(log n) benötigt und mehrfach aufgerufen wird, hat build insgesamt die Laufzeit O(n):

∑{h=0}^{⌊log n⌋} ⌈n/2^(h+1)⌉ O(h) = O(n ∑{h=0}^{⌊log n⌋} h/2^h) = O(n).

Dabei bezeichnet h die Baumhöhe; n/2^(h+1) beschreibt die Anzahl der Teilbäume auf der entsprechenden Ebene.

Schlüssel ändern und Elemente einfügen

Wird der Schlüssel eines Elements i mit decrease-key verringert, können nur die Vorgängerknoten die Heap-Eigenschaft verletzen. Die Kinder-Teilbäume von i bleiben gültige Heaps. Deshalb wird das Element bottom-up betrachtet: Es wird so lange mit seinem Elternknoten vertauscht, wie sein Schlüssel kleiner als der Schlüssel des Elternknotens ist. Die Laufzeit beträgt im Worst Case O(log n).

Beim Einfügen mit insert wird das Array am Ende um ein Element mit dem Wert ∞ erweitert. Anschließend wird decrease-key mit dem einzufügenden Schlüssel aufgerufen. Dadurch steigt das neue Element bei Bedarf nach oben, bis die Heap-Eigenschaft wiederhergestellt ist. Auch insert benötigt O(log n).

Entfernen und kleinstes Element

remove entfernt ein Element an einer beliebigen Position i. Dazu wird es mit dem letzten Array-Element vertauscht, danach wird das Array verkleinert. Das an Position i eingesetzte Element kann nun entweder größer als sein Elternknoten oder kleiner als dieser sein. Ist es größer, wird heapify verwendet und das Element nach unten verschoben. Ist es kleiner, wird decrease-key verwendet und das Element nach oben verschoben. Beide Richtungen sind nötig, weil ein Heap nur eine partielle Ordnung darstellt.

Ein Beispiel aus dem Artikel ist der Heap h1 = [0, 1, 2, 2, 1, 2, 2, 2, 2, 1]. Wird das Element an Index 5 gelöscht, entsteht nach dem Vertauschen und Entfernen des letzten Elements [0, 1, 2, 2, 1, 1, 2, 2, 2]. Das Element 1 an Index 5 ist kleiner als sein Elternknoten 2. heapify würde hier nichts ändern, weil es nur nach unten arbeitet; decrease-key muss das Element nach oben verschieben. Wird hingegen das letzte Element selbst entfernt, bleibt die Heap-Eigenschaft erhalten, und es darf keine weitere Korrektur an der nun außerhalb des Arrays liegenden Position erfolgen. remove hat im Worst Case die Laufzeit O(log n).

extractMin gibt das kleinste Element zurück und entfernt es. Da es im Min-Heap an der Wurzel steht, entspricht die Operation dem Aufruf von remove an Position 0 und benötigt O(log n). getMin gibt lediglich den Schlüssel an der Wurzel beziehungsweise an der ersten Array-Position zurück. Diese Operation verändert den Heap nicht und hat die konstante Laufzeit O(1).