Heapsort
Heapsort ist Selectionsort mit einer besseren Methode, den größten Wert zu finden. Es hält die unsortierten Werte in einem Heap, einem Baum in der Liste selbst, in dem der größte Wert immer oben steht. Ihn zu entnehmen und den Heap zu reparieren, braucht etwa log n Schritte statt eines vollständigen Durchsuchens.
Ein Baum in einer Liste
Ein binärer Heap ist ein Baum, der keine Zeiger braucht. Platz 0 ist die Wurzel, und die Kinder von Platz i sind die Plätze 2i + 1 und 2i + 2. Die Plätze 1 und 2 sind also die Kinder der Wurzel, die Plätze 3 bis 6 die nächste Ebene und so weiter. Jede Ebene ist voll, außer der letzten, die sich von links füllt. In einem Max-Heap ist jeder Elternknoten mindestens so groß wie seine Kinder, also steht der größte Wert immer an der Wurzel.
Versickern
Eine einzige Operation erledigt die ganze Arbeit. Um einen Wert versickern zu lassen, vergleichen Sie ihn mit seinen Kindern. Ist das größere Kind größer als der Wert, tauschen die beiden, und der Wert wird mit seinen neuen Kindern verglichen. Er stoppt, wenn kein Kind größer ist oder wenn er unten ankommt. Da der Baum nur etwa log₂ n Ebenen hat, braucht ein Versickern höchstens etwa 2 log₂ n Vergleiche.
Erst den Heap aufbauen, dann sortieren
Um den Heap aufzubauen, lassen Sie jeden Elternknoten versickern, vom letzten zurück bis zur Wurzel. Jeder Teilbaum ist ein Heap, bevor sein Elternknoten in ihn hinein versickert. Dann wird sortiert: Tauschen Sie die Wurzel, den größten Wert, mit dem letzten Wert des Heaps. Dieser Wert steht nun an seinem endgültigen Platz. Der Heap ist eins kürzer, und der Wert, der an der Wurzel gelandet ist, versickert, um ihn zu reparieren. Wiederholen Sie das, bis ein Wert übrig ist.
Ein Beispiel
Nehmen Sie 5, 1, 4, 2, 8. Beim Aufbau des Heaps versickert 1 unter die 8, dann 5 unter die 8, das ergibt 8, 5, 4, 2, 1. Jetzt wird 8 ans Ende getauscht; 1 landet an der Wurzel und versickert an 5 und 2 vorbei: 5, 2, 4, 1 | 8. Dann kommt 5 ans Ende, und 1 versickert an 4 vorbei: 4, 2, 1 | 5, 8. Zwei weitere Runden beenden die Liste: 1, 2, 4, 5, 8, nach 12 Vergleichen und 10 Vertauschungen.
Stärken und Schwächen
Heapsort braucht selbst im schlimmsten Fall Zeit proportional zu n log n und keinen zusätzlichen Speicher. Quicksort kann auf n² abfallen, und Mergesort braucht einen Puffer so lang wie die Liste. Daher ist Heapsort die sichere Rückfalllösung: Introsort, das die C++-Standardbibliothek nutzt, wechselt zu Heapsort, wenn die Partitionen von Quicksort schiefgehen. Auf echten Computern ist es meist langsamer als beide, weil es zwischen weit entfernten Stellen der Liste springt, und es ist nicht stabil. J. W. J. Williams veröffentlichte Heapsort zusammen mit dem binären Heap 1964.
Selbst ausprobieren
Öffnen Sie die App und drücken Sie „Schritt“. Der Baum über den Balken zeigt den Heap: Der versickernde Wert hat eine eigene Farbe, das Kind, mit dem er verglichen wird, ist hervorgehoben, und jede Vertauschung ist im Baum und in den Balken zu sehen. Sobald der Heap steht, sehen Sie, wie die Wurzel ans Ende getauscht wird, grün wird und aus dem Baum verschwindet.
Häufig gestellte Fragen
Welche Zeitkomplexität hat Heapsort?
O(n log n) im besten, mittleren und schlimmsten Fall. Der Aufbau des Heaps braucht O(n), und jede der n − 1 Entnahmen braucht O(log n). Heapsort sortiert in-place mit O(1) zusätzlichem Speicher.
Was ist der Unterschied zwischen Heapsort und Selectionsort?
Beide nehmen immer wieder den größten (oder kleinsten) verbleibenden Wert. Selectionsort findet ihn, indem es den ganzen unsortierten Teil durchsucht, jedes Mal mit n Vergleichen. Heapsort hält den unsortierten Teil in einem Heap, in dem der größte Wert schon oben steht, und das Reparieren des Heaps kostet nur etwa log n Vergleiche.
Wofür werden Heaps außer zum Sortieren verwendet?
Für Prioritätswarteschlangen: Ein Heap liefert sofort das größte (oder kleinste) Element und erlaubt, Elemente in etwa log n Schritten hinzuzufügen oder zu entfernen. Scheduler, der Dijkstra-Algorithmus für kürzeste Wege und Ereignissimulationen nutzen alle einen.
Ist Heapsort stabil?
Nein. Das Tauschen der Wurzel ans Ende verschiebt Werte über weite Strecken, daher können gleiche Werte ihre Reihenfolge ändern.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Heapsort ausprobieren