Binäre Heaps

Definition:
Ein Binärer Heap ist ein interner binärer höhenbalancierter Suchbaum mit Sortierungsbedingung:
Knotenschlüssel $\leq$ Schlüssel des rechten und linken Kindes
Seine Blätter werden von links nach rechts aufgefüllt (Binärbaum).

Bemerkung:
Die Sortierungsbedingung gewährleistet (im Gegensatz zum Suchbaum) das kleinste Element an der Wurzel des Baumes, so dass sich der Heap als Prioritätswarteschlange eignet. Die gezielte Suche nach einem Element macht i.A. keinen Sinn, denn der Aufwand beträgt $O(n)$.

Operationen:

1. $Insert$: Element als Blatt einfügen und ggf. Vertauschungen zur Wurzel hin durchführen

2. $ExtractMin$: Wurzel ausgeben, letztes Blatt als Wurzel einfügen und zu den Blättern hin vertauschen

3. $Delete$: Knoten löschen und durch letztes Blatt ersetzen, ggf. Vertauschungen zu den Blättern hin erforderlich

Alle Operationen in $O(\log n)$.