Heapsort

Kurz: Heapsort sortiert, indem es die Daten zu einem Max-Heap umbaut und dann immer wieder das größte Element ans Ende verschiebt.

Genauer: Er läuft immer in O(n log n), auch im schlechtesten Fall, und braucht keinen zusätzlichen Speicher. Dafür ist er in der Praxis meist langsamer als Quicksort, weil er den Speicher sprunghaft statt linear liest.

Im Detail

• Schritt 1: Das Feld wird in O(n) zu einem Max-Heap umgebaut: Von der Mitte rückwärts wird jeder Knoten nach unten „versenkt”.
• Schritt 2: Die Wurzel (größtes Element) tauscht mit dem letzten Element. Der Heap wird um 1 verkleinert und die neue Wurzel versenkt.
• Wiederholen, bis der Heap leer ist. Das Feld ist dann aufsteigend sortiert.
• Eigenschaften: nicht stabil, in place, unabhängig von der Vorsortierung.
• Einsatz: Als Rückfall in Introsort, falls Quicksort zu tief rekursiert. Vgl. Heap und Prioritätswarteschlange.

Siehe auch: Mergesort