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.

Heapsort Heapsort

Erstelle Lernmaterialien über Heapsort mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    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.

    Heapsort Sortiervorgang Erklärung StudySmarterAbb. 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.

    Heapsort Ursprünglicher Binärbaum Beispiel StudySmarterAbb. 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.

    Heapsort Max Heap Bedingung Beispiel StudySmarterAbb. 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.

    Heapsort Binärbaum nach Verschieben der Wurzel Beispiel StudySmarterAbb. 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.

    Heapsort Wiederhergestellte Max Heap Ordnung Beispiel StudySmarterAbb. 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.

    Heapsort Beweis Binärbaum Höhe und Anzahl Elemente pro Level StudySmarterAbb. 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 CaseAverage CaseWorst CasePlatzkomplexitätStabiles VerfahrenvergleichsbasiertIn-placeParallelisierbarkeititerativ/rekursiv
    O(n ∗ log n)O(n ∗ log n)O(n ∗ log n)O(1)NeinJaJaNeinBeides 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

    1. D.E. Knuth (1973). The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley
    2. George T. Heineman et al. (2008). Algorithms in a Nutshell. O'Reilly Media, Inc.
    Häufig gestellte Fragen zum Thema Heapsort

    Wie funktioniert Heapsort?

    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.

    Ist Heapsort stabil?

    Heapsort ist nicht stabil, weil er die Anordnung der Elemente zueinander vertauschen kann.

    Was ist ein Heap in der Informatik?

    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 wird welcher Sortieralgorithmus verwendet?

    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.

    Teste dein Wissen mit Multiple-Choice-Karteikarten

    Wahr oder falschBei einem Max Heap steht das größte Element in der Wurzel des Baums.

    Welches Element des Binärbaums wird bei Heapsort in den sortierten Bereich verschoben? 

    Welche Platzkomplexität hat Heapsort bei einer iterativen Implementierung?

    Weiter
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Heapsort Lehrer

    • 11 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

    Melde dich an für Notizen & Bearbeitung. 100% for free.

    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

    Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

    • Karteikarten & Quizze
    • KI-Lernassistent
    • Lernplaner
    • Probeklausuren
    • Intelligente Notizen
    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!