StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
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…
Entdecke über 200 Millionen kostenlose Materialien in unserer App
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenVielleicht 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.
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.
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.
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.
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
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
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].
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.
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.
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).
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).
Zum Verständnis von Heapsort und dem Vergleich mit anderen Sortieralgorithmen werden im Folgenden noch weitere Begrifflichkeiten erklärt.
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 gehört zu den vergleichsbasierten Sortieralgorithmen. Der Algorithmus vergleicht also immer zwei Elemente miteinander, um über ihre Anordnung in der Datenmenge zu entscheiden.
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.
Der Heapsort Algorithmus lässt sich nicht parallelisieren, weil er bei seinem Vorgehen ständig auf dem Array arbeitet und Elemente darin vertauscht.
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 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.
Im Gegensatz zu Quicksort hat Heapsort folgende Vorteile:
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.
Im ersten Schritt generiert Heapsort aus den zu sortierenden Elementen eine Heap Datenstruktur. Im zweiten Schritt sortiert er die Daten, indem er die Wurzel aus dem Heap entnimmt, sie mit dem letzten Element vom Heap ersetzt und den Heap von Neuem aufbaut. Dieser zweite Schritt wird so lange ausgeführt, bis der Heap nur noch ein Element beinhaltet.
Heapsort ist nicht stabil, weil er die Anordnung der Elemente zueinander vertauschen kann.
Ein Heap ist eine abstrakte Datenstruktur. Dabei handelt es sich um einen Binärbaum, bei dem alle Elemente eine bestimmte Heap-Bedingung erfüllen.
Wann welcher Sortieralgorithmus verwendet wird, hängt vom konkreten Anwendungsfall ab. Entscheidungskriterien sind zum Beispiel die Größe der Datenmenge, die gewünschte Leistungsfähigkeit des Algorithmus und ob ein stabiles Verfahren benötigt wird.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.