Heapsort ist ein Vergleichs-Sortierverfahren, das einen Heap (eine spezielle Baumstruktur) nutzt. Es besteht aus zwei Hauptschritten: Erstellen eines Heaps aus den Daten und wiederholtes Entnehmen des maximalen Elements und Neuanordnen.
heapsort(array):
n = Länge(array)
für i von n / 2 bis 0:
heapify(array, n, i)
für i von n-1 bis 0:
swap(array[0], array[i])
heapify(array, i, 0)
heapify(array, n, i):
größtes = i
links = 2*i + 1
rechts = 2*i + 2
wenn links < n und array[links] > array[größtes]:
größtes = links
wenn rechts < n und array[rechts] > array[größtes]:
größtes = rechts
wenn größtes != i:
swap(array[i], array[größtes])
heapify(array, n, größtes)
Gegeben sei das unsortierte Array: $[4, 10, 3, 5, 1]$.
Transformation des Arrays in einen Max-Heap:
Das größte Element (Wurzel des Heaps) wird entfernt und an das Ende des Arrays verschoben. Aktuell:
Wir entfernen 10: $[10, 5, 4, 1, 3] \to [3, 5, 4, 1, 10]$.
Nun wird der Heap neu strukturiert:
Nach dem Entfernen von 5 und dessen Neuordnung folgt die gleiche Prozedur:
Aktuell: $[5, 3, 4, 1] \to [4, 3, 5, 1]$ (5 wird entfernt).
Die Schritte wiederholen sich, bis das gesamte Array sortiert ist.
Endresultat: $[1, 3, 4, 5, 10]$