Beispiel:
Heaps lassen sich einfach als Arrays realisieren: Knoten werden einfach von der Wurzel beginnend auf jeder Ebene von links nach rechts durchnumeriert. Knoten a[i] hat Söhne a[2i] und a[2i+1].
Heap-Bedingung: a[i] > a[2i] und a[i] > a[2i+1]
maximales Element eines Heaps: Wurzel
Heap für zu sortierende Elemente herstellen,
maximales Element entfernen,
Heap-Bedingung wiederherstellen usw.
1) Mache letztes Element e zur Wurzel
2) Vertausche e jeweils mit seinem größten Sohn, bis Heap-Bedingung
erfüllt ist (lasse e versickern)