Vielleicht hast Du eine Zimmerpflanze zu Hause und gießt diese dann (hoffentlich) regelmäßig. Was passiert dabei mit dem Wasser? Natürlich versickert es in der Erde und sucht sich seinen passenden Platz.
Doch was hat das mit dem Heapsort-Algorithmus zu tun? Auch bei dem Algorithmus geht es um das Versickern eines Elements. Allerdings versickert es nicht in der Erde Deiner Zimmerpflanze, dafür aber in einem Binärbaum.
Heapsort Erklärung
Im Grunde handelt es sich bei dem Heapsort Algorithmus um eine Weiterentwicklung von Selection Sort. Die Besonderheit ist, dass die Sortierung bei Heapsort auf der Datenstruktur eines Heaps basiert.
Schaue Dir am besten die Erklärung zum Heap an, wenn Du nicht mehr genau weißt, was das ist.
Der Heapsort Algorithmus besteht aus den folgenden zwei Schritten.
Schritt 1: Heap generieren
Aus den zu sortierenden Daten wird zuerst eine Heap-Datenstruktur generiert. Das ist ein Binärbaum, bei dem alle Knoten eine bestimmte Heap-Bedingung erfüllen.
Das Herstellen der Heap-Bedingung in einem Binärbaum wird Heapify genannt. Zur Sortierung mit Heapsort kann sowohl ein Max Heap als auch ein Min Heap verwendet werden.
Die Bedingung des Max Heaps ist, dass der Wert des Elternknotens stets größer oder gleich den Werten seiner zwei Kindknoten ist. Die Bedingung des Min Heaps ist genau umgekehrt: Der Wert jedes Elternknotens muss kleiner oder gleich den Werten in den Kindknoten sein.
Schritt 2: Sortierung
Erst im zweiten Schritt beginnt die eigentliche Sortierung, die wie in Abbildung 1 gezeigt in 3 Schritten erfolgt. Hierbei wird aus dem Baum zunächst das Element in der Wurzel in den sortierten Bereich verschoben.
Warum kann man das Wurzelelement in den sortierten Bereich bewegen? Ganz einfach: Bei einem Max Heap ist es das größte Element bzw. bei einem Min Heap das kleinste Element der gesamten Menge.
Im zweiten Schritt versetzt man das letzte Element im Baum ganz nach oben und macht es somit zur neuen Wurzel. Dadurch kann es passieren, dass die Bedingung des Heaps nicht mehr für alle Knoten erfüllt ist.
Daher gilt es nun schließlich, die Bedingung des Heaps wiederherzustellen, sodass sie wieder für alle Knoten gilt. Dazu lässt man das Element in der Wurzel des Baums so lange nach unten wandern, bis es sich am richtigen Platz des Heaps befindet. Dieser Prozess wird auch Versickern genannt.
Abb. 1 - Heapsort Sortiervorgang
Damit ist die Heap-Bedingung für den Baum wieder erfüllt und man kann das Wurzelelement wieder in den sortierten Bereich verschieben.
Das beschriebene Vorgehen wird nun so oft wiederholt, bis in dem Baum nur noch ein Element übrig ist.
Das folgende Beispiel veranschaulicht noch einmal besser, wie Heapsort funktioniert, indem die Bedingung des Heaps wiederholt hergestellt wird, nachdem das Element in der Wurzel entnommen wurde.
Heapsort Beispiel
Gegeben sei das folgende Array mit den Elementen [7, 3, 9, 2, 1, 4]. Dieses soll nun mit Heapsort über den Aufbau eines Max Heaps sortiert werden.
Als Erstes erstellt man aus dem Array einen Binärbaum, indem man diesen einfach von links nach rechts mit den Elementen auffüllt und erhält den Binärbaum in Abbildung 2.
Abb. 2 - Ursprünglicher Binärbaum
Schritt 1: Heap generieren
Um aus dem Binärbaum einen Max Heap zu erhalten, wird im Baum von unten nach oben jeder Elternknoten auf die Heap-Bedingung hin geprüft.
Zur Erinnerung: Bei einem Max Heap muss der Elternknoten größer als die Kinder sein oder gleich. Ist also einer oder sind beide Kindknoten größer, so wird der Elternknoten mit dem größeren der beiden Kinder vertauscht.
In dem Beispiel ist die 9 größer als die 4. Das passt also, ebenso auch der Knoten mit der 3. Die 7 in der Wurzel ist allerdings kleiner als die 9 und verletzt somit die Bedingung eines Max Heaps, weshalb diese beiden Elemente vertauscht werden.
Da die vertauschte 7 selbst in einem Elternknoten stand, muss hierfür nochmals die Heap-Bedingung geprüft werden. Denn beim Vertauschen kann es passieren, dass die Heap-Bedingung für einen Teilbaum zerstört wird. Hier ist die 7 aber größer als die 4 und kann somit stehen bleiben.
Am Ende stehen im Array die Elemente in der Reihenfolge [9, 3, 7, 2, 1, 4] und der Max Heap sieht folgendermaßen aus. Der Heapify Prozess ist vollendet und die Heap-Bedingung erfüllt, wie man auch in Abbildung 3 erkennen kann.
Abb. 3 - Max Heap
Schritt 2: Sortierung
Jetzt erfolgt die eigentliche Sortierung. Die 9 wird aus der Wurzel in einen sortierten Bereich verschoben. An ihre Stelle tritt das letzte Element im Baum, also in dem Beispiel die 4. Diese wird zur neuen Wurzel des Baums, sodass sich ein Binärbaum wie in Abbildung 4 ergibt.
Abb. 4 - Binärbaum nach Verschieben der Wurzel
Die neue Wurzel wird nun im Binärbaum versickert, um wieder einen Max Heap zu erhalten, bei dem das größte Element in der Wurzel steht. Diese Heap-Bedingung nämlich wurde eventuell dadurch zerstört, dass das letzte Element in die Wurzel verschoben wurde.
Hier macht sich die Sortierung zunutze, dass die Heap-Bedingung für alle Teilbäume außer der Wurzel weiterhin gilt, weil dort nichts vertauscht wurde. Beim Versickern reicht es also, nur die Knoten zu betrachten, die verschoben wurden.
In dem Beispiel wird die 4 mit der 7 vertauscht. Der Elternknoten mit der 3 wird nicht weiter betrachtet, da er und seine Kinder nicht verändert wurden. Heapify wurde nun also erneut abgeschlossen und die Bedingung des Max Heaps ist wiederhergestellt.
Abb. 5 - Binärbaum wieder in Max Heap Ordnung
Als Nächstes wird die 7 in den sortierten Bereich verschoben, und die 1 wandert an die Wurzel des Baums. Der Sortierprozess beginnt also wieder von vorn und wird so lange wiederholt, bis nur noch ein Element im Baum verbleibt.
Am Ende ist das Array aus dem Beispiel absteigend sortiert, nachdem jedes Mal die Wurzel in den sortierten Bereich verschoben wurde: [9, 7, 4, 3, 2, 1].
Heapsort absteigend oder aufsteigend
In dem Beispiel wurde die Zahlenfolge absteigend sortiert, weil ein Max Heap verwendet wurde.
Genauso ist es aber denkbar, einen Min Heap zu verwenden, wo statt dem größten das kleinste Element in der Wurzel steht. Beim Verschieben des Elements aus der Wurzel in den sortierten Bereich ergibt sich damit eine aufsteigend sortierte Folge der Elemente.
Alternativ kann man ebenso die Zahlenfolge, die sich aus der Sortierung mit Max Heap ergeben hat, einfach umdrehen. Auch so erhält man eine aufsteigend sortierte Menge.
Heapsort Komplexität
Der Heapsort-Sortieralgorithmus kann in-place implementiert werden. Außer den Hilfsvariablen benötigt er dann keinen zusätzlichen Speicherplatz für die Elemente und kommt damit auf eine Platzkomplexität von O(1).
Spannend und ein wenig komplizierter wird es bei der Laufzeit von Heapsort.
Heapsort Laufzeit
Gleich vorweg: Heapsort gehört bei den vergleichsbasierten Algorithmen zu den schnellsten Verfahren. Der Algorithmus besitzt eine Zeitkomplexität von O(n · log n).
Zur Erinnerung: Laut O-Notation bezeichnet die Komplexitätsklasse O(n · log n) eine quasilineare Komplexität, bei der der Aufwand leicht mehr als linear mit der Eingabegröße wächst.
Doch wie setzt sich die Zeitkomplexität von Heapsort zusammen?
Beim Versickern wird der Baum einmal von oben nach unten traversiert. Dabei ist die Höhe eines Baumes mit n Elementen durch die Funktion log(n) festgelegt, also beträgt die Zeitkomplexität für diesen Schritt O(log n).
Hinzu kommt der Aufbau des Heaps bzw. Heapify Prozess aus Schritt 1, bei dem für jeden Knoten die Heap-Bedingung geprüft und die Versickern-Methode verwendet wird. Für diesen Schritt beträgt die Komplexität also O(n · log n).
Zusammengenommen hat Heapsort also eine Zeitkomplexität von O(n · log n).
Heapsort Beweis
Wie im letzten Abschnitt gezeigt, wird die Laufzeit beim Versickern eines Elements mit O(log n) angenommen. Doch wie kommt man darauf? Hier ist der Beweis dazu.
Satz: Zum Versickern benötigt man höchstens log2(n) Operationen. Somit liegt die Komplexität dafür in O(log n).
Beweis: Wie auch in Schritt 1 von Heapsort wird ein Heap stets von links aufgefüllt, bis ein Level des Baums vollständig aufgefüllt ist. Jedes Level i hält somit maximal 2i Elemente.
Betrachte zum Beispiel einen Heap mit 3 Levels. Die Wurzel ist das erste Level und hat 20 Elemente. Das zweite Level hat 21 Elemente, das dritte Level mindestens ein Element und höchstens 2² Elemente.
Nun kann der Heap erst ein viertes Level erhalten, sobald das dritte Level ausgeschöpft ist.
Die Gesamtzahl an Elementen n für einen Baum der Höhe h ergibt sich also folgendermaßen:
20 + 21 ... + 2h-2 + 1 ≤ n ≤ 20 + 21 ... + 2h-2 + 2h-1
Zur Erklärung: Die Gesamtzahl an Elementen n ergibt sich aus der Summe aller Elemente der vorherigen Levels 20 bis 2h-2 und zusätzlich einer variablen Anzahl an Elementen auf dem Level 2h-1, die zwischen 1 und 2h-1 liegen muss. Abbildung 6 verdeutlicht diesen Zusammenhang an einem Beispiel.
Abb. 6 - Anzahl Elemente ergibt sich aus Höhe des Binärbaums
Die obere Ungleichung kann man auch folgendermaßen schreiben:
2h-1 ≤ n ≤ 2h - 1
Durch schrittweise Umformung ergibt sich:
2h-1 + 1 ≤ n + 1 ≤ 2h
log2(2h-1 + 1) ≤ log2(n + 1) ≤ log2(2h) = h
Und da log2(2h) aufgelöst einfach h ergibt, braucht das Versickern eines Elements maximal log2(n + 1) Operationen und liegt somit in der Komplexitätsklasse O(log n).
Heapsort – Weitere Begrifflichkeiten
Zum Verständnis von Heapsort und dem Vergleich mit anderen Sortieralgorithmen werden im Folgenden noch weitere Begrifflichkeiten erklärt.
Heapsort stabil – instabil
Bei Heapsort handelt es sich nicht um einen stabilen Algorithmus. Es kann also passieren, dass er die Anordnung von gleichen Elementen zueinander verändert.
Heapsort vergleichsbasiert
Heapsort gehört zu den vergleichsbasierten Sortieralgorithmen. Der Algorithmus vergleicht also immer zwei Elemente miteinander, um über ihre Anordnung in der Datenmenge zu entscheiden.
Heapsort iterativ – rekursiv
Normalerweise wird Heapsort iterativ implementiert, aber auch eine rekursive Implementierung ist denkbar. Diese eignet sich jedoch eher für Übungszwecke, denn es ist zu bedenken, dass – ähnlich wie bei vielen anderen Sortieralgorithmen – bei der rekursiven Variante die Platzkomplexität des Algorithmus O(n) beträgt statt O(1).
O(1) beschreibt einen konstanten Aufwand eines Algorithmus. Der Aufwand ist dabei also unabhängig von der Eingabegröße. O(n) ist hingegen ein linearer Aufwand, also wächst der Aufwand dabei linear mit der Eingabegröße an.
Heapsort Parallelisierbarkeit
Der Heapsort Algorithmus lässt sich nicht parallelisieren, weil er bei seinem Vorgehen ständig auf dem Array arbeitet und Elemente darin vertauscht.
Heapsort Zusammenfassung
Die folgende Tabelle stellt noch einmal die Eigenschaften des Heapsort Algorithmus übersichtlich dar.
| Best Case | Average Case | Worst Case | Platzkomplexität | Stabiles Verfahren | vergleichsbasiert | In-place | Parallelisierbarkeit | iterativ/rekursiv |
| O(n ∗ log n) | O(n ∗ log n) | O(n ∗ log n) | O(1) | Nein | Ja | Ja | Nein | Beides möglich |
Heapsort Anwendung
Heapsort ist ein effizienter Sortieralgorithmus, für den eine Vielzahl von Szenarien denkbar ist. Er kann zum Beispiel verwendet werden, um eine große Liste von Zahlen zu sortieren oder um den kleinsten Wert in einem Datensatz zu finden.
Heapsort ist ein leistungsfähiger Algorithmus, der relativ einfach zu implementieren ist, was ihn zu einer beliebten Wahl für viele Anwendungen macht.
Heapsort vs. Quicksort
Im Gegensatz zu Quicksort hat Heapsort folgende Vorteile:
- Die Heapsort Zeitkomplexität lässt sich zuverlässiger bestimmen.
- Der Speicherbedarf von Heapsort ist minimal und steigt nicht mit der Anzahl zu sortierender Elemente an.
- Der nicht-rekursive Code des Heapsort Algorithmus ist leichter verständlich.
Dafür lässt sich Quicksort aber parallelisieren und eine gute Quicksort-Implementierung ist oft schneller und leistungsfähiger als der Heapsort Algorithmus. Dafür muss aber zusätzlicher Aufwand für eine Implementierung von Quicksort in Kauf genommen werden.
Heapsort – Das Wichtigste
- Heapsort Erklärung: Heapsort basiert auf der Datenstruktur des Heaps und nutzt zur Sortierung die Heap-Bedingung aus.
- Laufzeit Heapsort: Die Heapsort Komplexität beträgt für den benötigten Platz O(1) und O(n · log n) für die Zeitkomplexität.
- Heapsort Anwendung: Heapsort kann große Datenmengen effizient sortieren oder z. B. das kleinste Element in einer Menge finden.
- Heapsort vs. Quicksort: Quicksort ist beim Sortieren von Mengen oft schneller als Heapsort, allerdings ist der Aufwand für die Implementierung auch höher.
Nachweise
- D.E. Knuth (1973). The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley
- George T. Heineman et al. (2008). Algorithms in a Nutshell. O'Reilly Media, Inc.
Erklärungen 
Magazine 
