- Binärer Heap
-
Binärer Min-Heap
In der Informatik ist ein Binärer Heap eine Datenstruktur, genauer ein Heap, der sich als Vorrangwarteschlange einsetzen lässt, das heißt, es können in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in den Heap hineingelegt und stets das Element mit höchster Priorität entnommen werden.
Die Priorität der Elemente wird diesen durch Schlüssel aufgeprägt. Über der Menge der Schlüssel muss daher eine totale Ordnung bestehen, wie sie zum Beispiel die Kleiner-Relation (<) über den ganzen Zahlen darstellt.
Man unterscheidet zwischen:
- Min-Heap: Der kleinste Schlüssel bildet die Wurzel des Baumes und alle Nachfolger sind größer.
- Max-Heap: Der größte Schlüssel bildet die Wurzel des Baumes und alle Nachfolger sind kleiner.
Die beiden Strukturen und Operationen auf diesen Strukturen sind einander analog. Dieser Artikel beschränkt sich daher auf den Min-Heap.
Inhaltsverzeichnis
Operationen
Binäre Heaps unterstützen effizient die Operationen
- insert, zum Einfügen eines Elementes,
- remove, zum Entfernen eines Elementes,
- extractMin, zur Rückgabe und zum Entfernen eines Elementes mit minimalem Schlüssel (= höchster Priorität) und
- changeKey, zum Ändern des Schlüssels eines Elementes.
Alle Operationen lassen sich mit einer Worst-Case-Laufzeit von O(log n) implementieren, wobei n die Zahl der aktuell im Heap befindlichen Elemente ist.
Struktur
Ein Binärer Heap besteht aus einem Binärbaum, bei dem alle Schichten bis auf die letzte vollständig aufgefüllt sein müssen. Die letzte Schicht des Baumes muss linksbündig aufgefüllt werden. Diese Struktur garantiert, dass der Baum balanciert ist.
Zusätzlich muss der Binärbaum die Heap-Bedingung erfüllen: am Beispiel des Min-Heaps (siehe Abbildung) muss der Schlüssel jedes Kindes eines Knotens größer-gleich dem Schlüssel des Knotens selbst sein. Die Heap-Bedingung garantiert, dass sich an der Wurzel immer der Knoten mit dem kleinsten key befindet.
Häufig wird ein Binärer Heap nicht explizit mit Zeigern konstruiert, sondern durch ein Array abgebildet. Will man einen Binären Heap in einem Array speichern, so wird die Wurzel des Baums an der ersten Position im Array gespeichert. Die beiden Nachfolger eines Knotens an der i-ten Position werden an der 2i-ten und 2i+1-ten Position gespeichert, entsprechend der Kekulé-Nummerierung.
Implementierung der Operationen
Die Implementation der Operationen soll am Beispiel des Min-Heaps erklärt werden. Sie funktionieren für den Max-Heap analog.
Die Basis aller Operationen bildet die Funktion heapify, die dazu dient, die Heap-Bedingung wiederherzustellen, wenn an einer beliebigen Position im Baum ein Element oder sein Schlüssel ausgetauscht wurde. Die Funktion heapify arbeitet in zwei Phasen. In der ersten Phase wird das Element, welches die Heap-Bedingung verletzt, solange nach oben geschoben, indem es seine Position mit dem Vater tauscht, bis es in der Wurzel steht oder der Schlüssel des Vaters kleiner als der des Elementes selbst ist. In der zweiten Phase wird das Element solange nach unten geschoben (englisch sift-down von „Sieben“), indem es seine Position mit dem Kind tauscht, dessen Schlüssel am kleinsten ist, bis es Blatt ist oder die Kinder größere Schlüssel als das Element selbst besitzen.
Da die Höhe des Baumes logarithmisch von der Anzahl seiner Elemente abhängt, benötigt die Funktion heapify im Worst-Case logarithmische Laufzeit bzgl. der Größe des Heaps.
Das Einfügen eines Elementes mittels insert erfolgt nun, indem das neue Element einfach an das Ende der Heaps, also an die am weitesten links befindliche freie Stelle in der letzten Schicht, angefügt wird und anschließend mittels heapify die Heap-Bedingung für das neue Element wiederhergestellt wird.
Das Entfernen eines Elementes mittels remove geschieht, indem das zu entfernende Element aus seiner Position im Heap entfernt und an seine Stelle das am Ende des Heaps befindliche Element gesetzt wird. Anschließend wird mittels heapify die Heap-Bedingung für das verschobene Element wiederhergestellt.
Das Zurückgeben und Entfernen eines Elementes mittels extractMin gestaltet sich ähnlich wie remove. Das minimale Element befindet sich wegen der Heap-Bedingung an der Wurzel des Baumes und stellt damit das zu entfernende Element dar.
Das Ändern des Schlüssels eines Elementes mittels changeKey verlangt nach der Änderung ebenfalls lediglich einen Aufruf von heapify, um ggf. die Heap-Bedingung wiederherzustellen.
Bemerkungen
Die Operationen remove und changeKey setzen voraus, dass man die Position der entsprechenden Elemente im Heap kennt. Im Allgemeinen ist es nämlich nicht möglich, effizient ein Element im Heap zu suchen. Daher muss die Operation insert einen Zeiger auf den Behälter für das eingefügte Element zurückliefern, den sich das aufrufende Programm im Bedarfsfall an geeigneter Stelle merkt.
Anwendung
Die Hauptanwendung binärer Heaps liegt im Sortierverfahren Heapsort. Bei diesem bietet sich die Speicherung des Heaps als Array an. Eine weitere Anwendung ist eine Prioritätswarteschlange. Dabei handelt es sich um eine Schlange mit der Zusatzeigenschaft, dass die Elemente eine Priorisierung kennen und als erstes Element das Element mit der größten Priorität steht. Ein binärer Max-Heap implementiert diese Warteschlange effizient.
Siehe auch
Wikimedia Foundation.
