Interaktive Demo
Heapsort-Visualisierung
Heapsort ordnet ein Array zuerst als binären Max-Heap an und verschiebt dann immer wieder das größte Element ans Ende. Er braucht immer O(n log n) Schritte und kommt ohne zusätzlichen Speicher aus.
Klicke auf „Nächster Schritt“, um Schritt für Schritt vorzugehen, oder auf „Abspielen“, um den Algorithmus selbst laufen zu lassen.
Ablauf
Legende
- Heap-Element
- Versickerndes Element
- Verglichenes Kind
- Größeres Kind
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n log n)
Auch ein vorsortiertes Array muss erst zum Heap aufgebaut und wieder abgebaut werden.
Mittlerer Fall
O(n log n)
Bei jeder der n Entnahmen versickert die neue Wurzel durch etwa log n Ebenen.
Schlechtester Fall
O(n log n)
Der Heap hat nur log n Ebenen, keine Eingabe kann das Versickern verlängern.
Zusätzlicher Speicher
O(1)
Der Heap liegt im Array selbst, nur wenige Hilfsvariablen sind nötig.
Stabil
Nein
Das Verschieben der Wurzel ans Ende überspringt gleiche Elemente.
In-place
Ja
Der Heap wird innerhalb des Arrays auf- und abgebaut.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
1. Der Heap ist das Array
Das Array wird als Binärbaum gelesen: Die Kinder des Elements an Index i liegen an 2i + 1 und 2i + 2. Der Baum über den Balken zeigt genau dieselben Elemente.
2. Max-Heap aufbauen
Vom letzten Elternknoten an sinkt jedes Element nach unten, indem es mit seinem größeren Kind tauscht, bis es nicht kleiner als seine Kinder ist. Danach steht das Maximum an der Wurzel.
3. Sortieren
Die Wurzel wird mit dem letzten Heap-Element getauscht, damit steht das Maximum an seiner endgültigen Position. Der Heap schrumpft um eins und die neue Wurzel versickert, bis der Heap leer ist.