Heapsort – Funktionsweise

Heapsort beruht auf der Heapeigenschaft, nämlich das jeder Knoten größer als seine Kindknoten sein muss.

Aus einer unsortierten Folge wird ein Anfangsheap erstellt. Dies geschieht Anhand von versickern derjenigen Folgenelemente, welche die Heapeigenschaft nicht erfüllen. Beim Aufbau des Anfangsheaps wird die Liste von Hinten durchgangen.

Ist ein Ausgangsheap erstellt worden, und möchte man die Folge aussteigend sortieren, vertausche man das erste und das letzte Folgenelement. Das Letzte ist nun das größte und wird nicht mehr betrachtet.

Die neue Folge wird wieder Analog bearbeitet, bis die zu sortierende Folge nur noch aus einem Element besteht.