Heapsort
Über diese App
Heapsort Schritt für Schritt — Heap aufbauen, Heapeigenschaft herstellen und schrittweise sortieren.
Wie Heapsort funktioniert
Heapsort nutzt einen Max-Heap: einen vollständigen Binärbaum, in dem jeder Elternknoten mindestens so groß ist wie seine Kinder. Der Baum steckt direkt im Array, die Kinder von Position i liegen bei 2i+1 und 2i+2. Zuerst wird das Array in einen Heap verwandelt, indem man von der letzten inneren Position rückwärts jeden Knoten versickern lässt. Dann steht das Maximum an der Wurzel. Es wird mit dem letzten Element des Heaps getauscht, der Heap schrumpft um eins, und die neue Wurzel versickert, bis die Heapeigenschaft wieder gilt. Das wiederholt sich, bis alles sortiert ist. Laufzeit: O(n log n) in jedem Fall.
Was die App zeigt
Oben steht der Binärbaum, darunter dasselbe Array als Liste. Hervorgehoben werden die Wurzel, der gerade versickernde Knoten und das Eltern-Kind-Paar, das verglichen oder getauscht wird. Hinten im Array wächst die fertig sortierte Region. Eine Phasenanzeige unterscheidet Aufbau, Sortieren und Fertig, ein Zähler nennt Heap-Größe und Anzahl sortierter Elemente, ein Text erklärt jeden Schritt.
Selbst ausprobieren
Gib eigene Zahlen ein und gehe Schritt für Schritt vor und zurück oder lass den Ablauf abspielen. Beobachte, wie nach jedem Tausch das größte verbliebene Element wieder an die Wurzel steigt, und wie Baum und Array immer dasselbe zeigen. Gut geeignet ist eine absteigend sortierte Liste: Sie ist bereits ein Max-Heap, der Aufbau kommt dann ohne einen einzigen Tausch aus.
Häufige Fragen
- Was ist ein Max-Heap?
- Ein Max-Heap ist ein vollständiger Binärbaum, in dem jeder Knoten mindestens so groß ist wie seine Kinder. Deshalb steht das größte Element immer an der Wurzel. Gespeichert wird er meist als Array: Die Kinder von Index i stehen an 2i+1 und 2i+2, der Elternknoten an (i−1)/2 abgerundet.
- Was bedeutet Versickern (sift down)?
- Ein Knoten, der kleiner ist als eines seiner Kinder, wird mit dem größeren Kind getauscht und wandert so lange nach unten, bis er größer oder gleich beiden Kindern ist oder ein Blatt erreicht. Das stellt die Heapeigenschaft in O(log n) Schritten wieder her.
- Welche Laufzeit hat Heapsort?
- Heapsort braucht im besten, mittleren und schlechtesten Fall O(n log n) und sortiert in place ohne zusätzlichen Speicher. Der Heap-Aufbau allein kostet nur O(n). Stabil ist Heapsort nicht.
- Was zeigt die Heapsort-App?
- Baum und Array nebeneinander, mit hervorgehobener Wurzel, versickerndem Knoten und verglichenem Paar. Du gibst eigene Zahlen ein, gehst jeden Schritt einzeln durch und siehst hinten im Array die sortierte Region wachsen.
Fach: Informatik
Mehr aus Informatik
- Ackermann-Funktion
- Aufzug-Simulator
- Binär-Werkstatt
- Binäre vs. lineare Suche
- Collatz-Problem (3n+1)
- CPU-Innenleben
- Das Innere austauschen
- Ein Frame in 16 Millisekunden — wie eine Game-Engine ein Bild rechnet (3D)
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps