Heap-Sort

Heap bedeutet so viel wie Halde, Haufen.
Vor dem eigentlichen Sortieren wird erst aus dem unsortierten Array erst einmal ein Heap aufgebaut - ein binärer Baum wird mit den Elementen der Folge gefüllt.


In einem Heap (rechte Abb.) ist der Wert der Söhne jedes Knotens immer kleiner als der Wert des Knotens selbst. Der größte Wert steht stets in der Wurzel (im Beispiel 46).

1. Aus der Eingabefolge von sortierbaren Elementen wird ein binärer Baum konstruiert.
2. In diesem binären Baum wird so lange ein Knoten mit dem größeren seiner Söhne vertauscht , bis das größte Element an der Wurzel steht. Das Ganze wird Heap genannt.
3. Das Element mit dem kleinsten Wert, also das letzte, das am tiefsten sitzende Blatt, kommt auf die Stelle der Wurzel.
Nun wandert, versickert das Element von der Wurzel in das Array.
4. Weiter geht es mit 2., bis die Wurzel leer ist.