Heapsort (Algorithmus 2.7)

So geht’s: Oben steht der Heap als Baum, darunter dasselbe Array als Balken, beide mit den Heap-Plätzen 1 bis n. Orange ist das Element, das gerade absinkt, blau das Kind, mit dem es verglichen wird, grün ein Tausch. In Phase 2 wandert das Maximum jeweils nach hinten. Dort steht es endgültig, im Baum nur noch gestrichelt und bei den Balken hellblau. „Bis sink fertig“ springt zum Ende des aktuellen sink, „Bis Heap fertig“ zum Ende von Phase 1. Das Protokoll zeigt wie Abbildung 2.32 nach jedem sink das Array, mit n und k des Aufrufs. Von sink bewegte Elemente sind hervorgehoben, endgültig sortierte grau.

Erklärung

Heapsort (Algorithmus 2.7) nutzt den Heap aus [12] direkt im Eingabearray, ohne Zusatzspeicher. Zwei Phasen:

Phase 1: Heap-Konstruktion (die for-Schleife)

• sink(a, k, N) für k = N/2 runter bis 1. Die Blätter (hintere Hälfte) sind für sich schon Mini-Heaps, also fängt man beim letzten Knoten mit Kindern an und arbeitet sich zur Wurzel vor.
• Dieses Bottom-up-Verfahren braucht weniger als 2N Vergleiche, also linear. Schneller als N-mal insert.
• In der Tabelle: Aus SORTEXAMPLE wird nach k = 5, 4, 3, 2, 1 die heap-geordnete Folge X T S P L R A M O E E. Das X steht vorn als Maximum.

Phase 2: Sortdown (die while-Schleife)

• exch(a, 1, N--): Das Maximum an der Wurzel wird mit dem letzten Element getauscht und gilt ab jetzt als fertig. Der Heap schrumpft um eins.
• sink(a, 1, N): Das nach oben getauschte Element sinkt ab, die Heap-Ordnung stimmt wieder.
• Das wiederholt sich, bis der Heap leer ist. Von hinten füllt sich das Array mit den größten Elementen: erst X, dann T, dann S …
• In der Tabelle: Rot = von sink bewegt, grau = rechts schon endgültig sortiert.

Indizes: Der Heap rechnet mit 1..N. Damit das echte Java-Array a[0..N-1] sortiert wird, ziehen less() und exch() intern jeweils 1 vom Index ab.

Kosten:

• Weniger als 2N lg N + 2N Vergleiche, garantiert, auch im schlimmsten Fall.
• In place, kein Zusatzspeicher.
• Nicht stabil.

Einordnung: Heapsort ist das einzige der bisherigen Verfahren, das beides garantiert: N lg N im schlimmsten Fall und kein Zusatzspeicher. In der Praxis ist es trotzdem meist langsamer als Quicksort, weil sink quer durchs Array springt (Index k zu 2k) und damit den Prozessor-Cache schlecht ausnutzt. Deshalb wird es gern als Absicherung eingesetzt, z. B. in Introsort, wenn Quicksort zu tief rekursiert.