- Versickert
- Verglichen
- Getauscht
- Platziert
Heapsort
Heapsort liest die Liste als Binärbaum und ordnet sie zu einem Max-Heap um, in dem jeder Elternknoten mindestens so groß ist wie seine Kinder. Dann steht der größte Wert oben. Tauschen Sie ihn ans Ende, wo er bleibt, reparieren Sie den Heap und wiederholen Sie das. Die App zeichnet den Heap als Baum über den Balken, so können Sie jeden Wert beim Versickern verfolgen. Drücken Sie „Abspielen“, um die Sortierung anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Der Baum über den Balken zeigt dieselben Werte als Heap. Die Kacheln zählen Vergleiche, Vertauschungen und die aus dem Heap entnommenen Werte. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene Zahlen ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie die Anzahl der Balken und ihre Startreihenfolge: zufällig, fast sortiert, umgekehrt oder mit wenigen verschiedenen Werten. Oder geben Sie eigene Zahlen ein.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Sortierung zu springen.
- Beobachten Sie den Baum: Zuerst versickert jeder Elternknoten, bis der Heap steht, dann wird die Wurzel ans Ende getauscht und der Heap schrumpft um eins.
Wie Heapsort funktioniert
Lesen Sie die Liste als Baum: Der Wert an Platz i hat seine Kinder an den Plätzen 2i + 1 und 2i + 2. Bauen Sie einen Max-Heap auf, indem Sie jeden Elternknoten versickern lassen, beginnend mit dem letzten: Solange ein Wert kleiner ist als sein größeres Kind, tauschen die beiden. Hält die Wurzel den größten Wert, tauschen Sie ihn mit dem letzten Wert des Heaps. Dieser Wert ist nun endgültig, der Heap ist eins kürzer, und die neue Wurzel versickert, damit er wieder ein Heap ist. Wiederholen Sie das, bis der Heap leer ist.
Immer n log n, in-place
Der Baum hat etwa log₂ n Ebenen, daher braucht jedes Versickern höchstens etwa 2 log₂ n Vergleiche und der Aufbau des Heaps weniger als 2n. Damit macht Heapsort im schlimmsten Fall etwa 2n log₂ n Vergleiche, ohne Puffer: bei 40 Werten höchstens 352. Anders als Quicksort kennt Heapsort keine ungünstigen Eingaben, und anders als Mergesort braucht es keinen zusätzlichen Speicher. In der Praxis ist es meist langsamer als beide, weil es in der Liste hin und her springt, und es ist nicht stabil.
Häufig gestellte Fragen
Wie funktioniert Heapsort?
Heapsort macht aus der Liste einen Max-Heap, einen in der Liste gespeicherten Baum, in dem jeder Elternknoten mindestens so groß ist wie seine Kinder. Dann tauscht es immer wieder den größten Wert, an der Wurzel, ans Ende des Heaps und lässt die neue Wurzel versickern, um den Heap zu reparieren.
Was ist ein Heap?
Ein vollständiger Binärbaum, der ohne Zeiger in einer Liste gespeichert ist: Die Kinder von Platz i sind die Plätze 2i + 1 und 2i + 2. In einem Max-Heap ist jeder Elternknoten mindestens so groß wie seine Kinder, also steht der größte Wert immer an der Wurzel, auf Platz 0.
Warum ist der Aufbau des Heaps schnell?
Die meisten Werte liegen weit unten im Baum und können nur ein oder zwei Ebenen versickern. Summiert man die Arbeit über alle Ebenen, ergibt das weniger als 2n Vergleiche für den ganzen Aufbau, nicht n log n.
Ist Heapsort stabil?
Nein. Das Tauschen der Wurzel ans Ende verschiebt Werte über weite Strecken, daher können gleiche Werte ihre Reihenfolge ändern.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Sortierung läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor