binärer Heap

Ein Binärer Heap ist eine Datenstruktur aus der Informatik zum effizienten Sortieren von Elementen. Das asymptotisch optimale Sortierverfahren Heapsort verwendet als zentrale Datenstruktur einen binären Heap. Des Weiteren wird der binäre Heap zur Implementierung einer Vorrangwarteschlange, in der das Element mit der höchsten Priorität effizient abgefragt und entfernt werden kann, verwendet.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. In der Literatur wird oft der Zusatz binär weggelassen, so dass je nach Zusammenhang der Heap als archetypische (binäre) Heap-Struktur (implementiert in einem Array) oder die Klasse aller Heap-Datenstrukturen gemeint ist.Des Weiteren wird bei Verwendung der Ordnungsrelation bzw. ein Heap als Min-Heap bzw. Max-Heap bezeichnet.Da sich die Operationen im Min- und Max-Heap nur durch die verwendete Ordnungsrelation unterscheiden, wird im Folgenden der binäre Heap und die Operationen darauf am Beispiel des Min-Heap definiert.