Informatik

Wie funktioniert Heapsort?

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.

Schritte

• Heap erstellen: Umwandlung des Arrays in einen Max-Heap.
• Sortieren: Das größte Element wird entfernt, das letzte Element wird an die Wurzel des Heaps gesetzt. Danach wird der Heap neu strukturiert.

Pseudocode

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)

Beispiel

Gegeben sei das unsortierte Array: $[4, 10, 3, 5, 1]$.

Schritt 1: Heap erstellen

Transformation des Arrays in einen Max-Heap:

Schritt 2: Sortieren

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,10] \to [4,3,1,5,10]$ (5 ist an seiner endgültigen Position).

Die Schritte wiederholen sich, bis das gesamte Array sortiert ist.

Endresultat: $[1, 3, 4, 5, 10]$