Binärer Heap

Ein Binärer Heap ist ein spezieller Binärbaum mit den Eigenschaften, dass jeder Knoten, der einen rechten Nachfolger hat, auch einen linken Nachfolger hat, und der Wert jedes Knotens jeweils größer ist als der seiner Nachfolger.

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 Arrayposition i werden an den Positionen 2*i und 2*i+1 gespeichert.