In der Informatik ist ein Binärer Heap eine Datenstruktur, genauer ein Heap, der sich als Prioritätswarteschlange einsetzen lässt, dass heißt es können in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in den Heap hineingelegt und stets das Elemente 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.
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.
Aufbau
Ein Binärer Heap ist ein spezieller Binärbaum, der die Heap-Eigenschaft erfüllt, das heißt der Schlüssel jedes Kindes eines Knotens ist größer als der seines Vaters. Ferner sind mit Ausnahme der Letzten alle Stufen des Baumes voll besetzt. Die letzte Stufe muss aber von links her aufgefüllt werden.
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 Position 1 im Array gespeichert. Die beiden Nachfolger eines Knotens an der Position i werden an den Positionen 2i und 2i+1 gespeichert.
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 von Binären Heaps liegt im Sortierverfahren HeapSort. Bei diesem bietet sich die Speicherung des Heaps als Array an.
Siehe auch: Heap, Binomial-Heap, Fibonacci-Heap