Heapsort

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.

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.

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.

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.

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).

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 log₂(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 2ⁱ Elemente.

Die Gesamtzahl an Elementen n für einen Baum der Höhe h ergibt sich also folgendermaßen:

2⁰ + 2¹ ... + 2^h-2 + 1 ≤ n ≤ 2⁰ + 2¹ ... + 2^h-2 + 2^h-1

Zur Erklärung: Die Gesamtzahl an Elementen n ergibt sich aus der Summe aller Elemente der vorherigen Levels 2⁰ bis 2^h-2 und zusätzlich einer variablen Anzahl an Elementen auf dem Level 2^h-1, die zwischen 1 und 2^h-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:

2^h-1 ≤ n ≤ 2^h - 1

Durch schrittweise Umformung ergibt sich:

2^h-1 + 1 ≤ n + 1 ≤ 2^h

log₂(2^h-1 + 1) ≤ log₂(n + 1) ≤ log₂(2^h) = h

Und da log₂(2^h) aufgelöst einfach h ergibt, braucht das Versickern eines Elements maximal log₂(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).

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.

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.