How it works?

Ein binärer Heap befindet sich in einem einfachen Array. Für den Knoten am Index i (0-basiert) befinden sich seine Kinder bei 2*i + 1 und 2*i + 2. Diese Indizierung ist der ganze Trick, der es ermöglicht, einen Baum in einem Array abzubilden.

Schritt-für-Schritt-Prozess:

1. Max-Heap erstellen: ordnen Sie das Array so um, dass jeder Elternknoten >= seine Kinder ist. Der größte Wert landet an Index 0.
2. Das Maximum extrahieren: tauschen Sie die Wurzel (das Größte) mit dem letzten Element des Heaps aus und verkleinern Sie dann den Heap um eins, sodass das Größte nun am Ende in seiner endgültigen sortierten Position steht.
3. Mit Sift-Down reparieren: die neue Wurzel könnte deplatziert sein, also verschieben Sie sie nach unten (sift-down) (tauschen Sie sie mit ihrem größeren Kind aus, wiederholen Sie dies), bis die Heap-Eigenschaft wieder erfüllt ist.
4. Wiederholen Sie dies, bis der Heap leer ist. Das Array ist nun aufsteigend sortiert.

Beispiel an [4, 10, 3, 5, 1]:

• Max-Heap erstellen: [10, 5, 3, 4, 1].
• Tauschen Sie die Wurzel 10 an das Ende und führen Sie Sift-Down aus, dann wiederholen Sie dies für 5, 4, 3.
• Ergebnis: [1, 3, 4, 5, 10].