Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

37.2.3 Heapsort

37.2.3 Heapsort

Das letzte Sortierverfahren welches ich besprechen werde, ist meiner Meinung nach das komplizierteste, da man nicht wirklich auf Anhieb sieht, warum dieser Algorithmus funktioniert. Aber da ich Ihnen auch mal andere Herangehensweisen zeigen möchte, habe ich es mit aufgenommen.

Die Grundidee ist, dass man die Liste als ein Binärbaum betrachtet, also ein Baum mit einer Wurzel bzw. einem Vaterknoten und zwei Kindern. Jener Baum wird dann immer so modifiziert, dass der Vater größer ist als beide Kinder und das linke Kind größer ist als das rechte. Dies nennt man "MaxHeapify". Damit sorgt man dafür, dass das größte Element am Anfang der Liste steht. Jenes wird dann mit dem letzten Element der unsortierten Liste vertauscht, was zur Folge hat, dass es quasi vor den Sortierten Bereich gehangen wird. Das selbe Spiel wird dann mit der um eins verkleinerten Liste gemacht.

Nun wird aber kein wirklicher Baum erzeugt, da der Verwaltungsaufwand zu groß und somit das Verfahren nicht effizient wäre. Die Vorbereitungen und das eigentliche Sortieren, werden alle im Ausgangscontainer vorgenommen. Jener wird nur rein logisch wie ein Baum behandelt. Dies ist auch garnicht schwer, wenn man es mit einem Binärbaum zu tun hat. Es wird einfach davon ausgegangen, dass das erste Element die Wurzel ist und die Kinder eines jeden Vaters, stehen an der Position des Vaters mal zwei, bzw. mal zwei plus eins. So hat die Wurzel "eins" die Kinder "zwei" und "drei" (1 x 2 = 2 und 1 x 2 + 1 = 3). Der Vater "zwei", hat die Kinder "vier" und "fünf" (2 x 2 = 4 und 2 x 2 + 1 = 5). Sie sehen also, dass dieses Verfahren sehr gut funktioniert. In den folgenden Grafiken werde ich immer Bäume aufmalen, damit Sie besser sehen, was passiert.

Bevor das Sortierverfahren losgehen kann, muss aus der Liste ein Ausgangsheap erzeugt werden. Dies nennt man "BuildMaxHeap". Dies sieht wie folgt aus.

Vorbereitungen für Heapsort

Die Liste wird von hinten Durchlaufen und aus den Elementen zwischen Position und Ende, die Heapeigenschaft hergestellt. Es wird jeder Vater (vom Untersten an) mit dem untersten Kind verglichen und ggf. vertauscht, falls das Kind einen größeren Wert hat. Dies alleine sorgt zwar nicht dafür, dass dieser Teil komplett richtig ist, aber falls Fehler entstehen, wie man das bei der Teilliste [2, 5, 3, 4] sieht, so werden jene im nächsten Schritt automatisch korrigiert. Dies liegt daran, dass im nächsten Schritt die Elemente ganz anders interpretiert werden (aus Blättern können Knoten werden und umgekehrt).

Das Vorbereiten der Liste dauert am längsten (lineare Laufzeit), aber die Vorbereitungen sorgen dann später dafür, dass im Schnitt nur noch die Hälfte überprüft werden muss, da ein Baum entsteht, welcher den Anforderungen entspricht. Nun kann das eigentliche Sortieren beginnen. In folgender Grafik sehen Sie den ersten Durchlauf.

Erster Sortierschritt des Heapsort Verfahrens

Am Anfang eines jeden Durchlaufes, wird wie erwähnt, das erste Element mit dem letzten Vertauscht. Am Anfang stellt genau jenes Element das größte in der gesamten Liste dar. Die 7 wird also mit der 2 getauscht und kann als sortiert betrachtet werden. Jetzt ist allerdings die Heapeigenschaft für den unsortierten Bereich nicht mehr gegeben und deswegen wird "MaxHeapify" aufgerufen. Die Grundidee ist hier, dass der Baum hauptsächlich oben kaputt ist (weil dort ja was vertauscht wurde) und jetzt ein paar kleinere Korrekturen vorgenommen werden müssen. Die Wurzel wird also mit seinen Kindern verglichen und es wird ggf. etwas getauscht. In meinem Beispiel die 2 mit der 6. Jetzt muss noch gewährleistet werden, dass das linke Kind größer ist als das rechte. Ggf. muss wieder getauscht werden, was in meinem Beispiel dazu führt, dass die 2 mit der 5 getauscht wird. Jetzt folgt ein sehr theoretischer Ansatz. Man geht davon aus, dass, wenn ein Teil des Baumes den Heapeigenschaften genügt, alle darunter liegenden Unterbäume, auch jenen Eigenschaften genügen. Es wird also erst geprüft, ob der Vaterknoten 5 größer ist als 4 und 1 und ob die 4 größer ist als die 1. Ist dem so, muss nichts weiter gemacht werden. Aus Gründen der Übersichtlichkeit, ist die Liste nur verhältnismäßig klein, sodass ich jetzt nicht so richtig deutlich machen kann, dass hier wirklich nichts mehr gemacht werden muss. Aber hingen Theoretisch unter der 4 und der 1 weitere Bäume, so bräuchte da nichts gemacht werden, was zur Folge hat, dass man sich grob gesagt, um die Hälfte der Elemente nicht mehr kümmern muss. Nun muss nach das zweite Kind, also die 2 und ihre Kinder, kontrolliert werden. Dies hat zur Folge, dass die 2 mit der 3 getauscht wird. Da die 2 jetzt neues Kind ist und somit für alle Unterbäume die Heapeigenschaft nicht mehr stimmen könnte, wird hier nochmals geprüft. Da die 2 ebenfalls ein Blatt ist, ist dieser Schritt beendet.

Zweiter Sortierschritt des Heapsort Verfahrens

Jetzt geht der ganze Spaß von vorne los. Das erste Element wird wieder mit dem letzten Element des unsortierten Bereiches vertauscht, was zur Folge hat, dass die 6 vor den sortierten Bereich, also die 7, kommt. Nun wird wieder der Baum "aufgebaut" und von oben her geschaut, ob was getan werden muss. Die 2 wird also mit der 5 getauscht. Da die 2 jetzt nicht gröer ist als ihre Kinder, wird wieder getauscht und so landet die 4 eine Ebene weiter oben. Da die 4 größer ist als ihr rechter Bruder. Ist wieder Feierabend. Warum wurde aber jetzt erst der Unterbaum repariert und dann erst mit dem Bruder verglichen? Vorhin war es doch anders herum! Dies ist immer abhängig von der Anzahl und der Verteilung der Elemente im Baum und ist der Tatsache verschuldet, dass ich keinen richtigen Baum, sondern eine habe. Je nach Längen der Liste, wird bei gerader Anzahl der Elemente, erst der Brudervergleich vorgenommen, bzw. bei ungerader Länge, erst der Kindvergleich.

Dritter Sortierschritt des Heapsort Verfahrens

Nachdem die Heapeigenschaft erneut wiederhergestellt ist, geht das Spiel nochmals von vorne los. Wieder der Tausch des ersten mit dem letzten Element vorgenommen und "MaxHeapify" aufgerufen. Hier sehen Sie wieder schön, dass jetzt erst der Bruder verglichen wird, obwohl man auch erst die 1 mit der 2 tauschen könnte.

Ich denke, jetzt sollte so ungefähr klar sein was passiert und wenn nicht, dann ist dies nicht so schlimm, da dieses Verfahren wie Shellsort, eher selten benutzt wird. Der Vollständigkeit halber sehen Sie jetzt noch die drei letzten Schritte.

Vierter Sortierschritt des Heapsort Verfahrens

Fünfter Sortierschritt des Heapsort Verfahrens

Sechster Sortierschritt des Heapsort Verfahrens

Abschließend sei noch erwähnt, dass die Reparatur immer nur in dem Teilbaum durchgeführt werden, welcher den kleineren Vater hat. Somit betrachtet man erst die Hälfte, dann nur noch ein Viertel, dann ein Achtel und so weiter. Es kommt dann lediglich noch der Vergleich des Bruders hinzu. Wir haben also auch logarithmische Laufzeit. Allerdings braucht man in der Regel mehr vergleiche als bei den vorhergehenden Verfahren, was diesen Sortieralgorithmus in der Praxis unattraktiv macht.

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012