Einer der bekannten höheren Sortieralgorithmen auf dieser Welt ist HeapSort, der eine meiner Meinung nach wirklich geniale Anwendung eines Heap-Baums ist. HeapSort hat sich, seitdem ich mir sämtliche wichtigeren Sortieralgorithmen angesehen habe, schlagartig zu meinem Lieblingsalgorithmus entwickelt (rein theoretisch gesehen -- ich weiß, dass QuickSort oft effektiver ist, aber HeapSort ist eleganter). Aus diesem Grund habe ich beschlossen, der Allgemeinheit weitere Informationen und eine Beschreibung der Funktionsweise zur Verfügung zu stellen.
Grundlagen
Zutaten
HeapSort verwendet, wie der Name schon sagt, einen Heap zum Sortieren. Ein Heap ist ein spezieller Baum, der die folgenden Eigenschaften erfüllt:
- Es handelt sich um einen Binärbaum (d.h. jeder Knoten hat höchstens zwei Nachfolger)
- Der Baum ist linksvollständig (d.h. jeder linke Nachfolgerknoten, der einen Bruder mit Kindern hat, muss auch Kinder haben. In anderen Worten, der Baum ist mindestens bis zur vorletzten Ebene vollständig und in der letzten Ebene dürfen nur rechts Knoten fehlen)
- Der Wert jedes Knotens ist größer als seine Nachfolger
So banal es sich anhört, damit ist der Suchalgorithmus schon fast fertig. Linksvollständige Binärbäume haben nämlich einige nützliche Eigenschaften... man kann sie zum Beispiel ohne Probleme in einem einzigen Array speichern, und man kann grundsätzlich in konstanter Zeit die Nachfolger (N(x) = x*2 (links) bzw. x*2 + 1 (rechts)) bzw. den Vorgänger (V(x) = |_ x/2 _|) eines Knotens berechnen. Also kann man, sobald man den Heap hergestellt hat, einfach immer wieder das oberste Element entfernen (es ist ja das höchste Element und ergo das letzte Element in der fertig sortierten Folge) und dann den Heap "reparieren", indem ein paar Knoten vertauscht werden. Wenn man das oft genug wiederholt, ist irgendwann das Array sortiert. Toll, nicht wahr? Und so geht's:
Der Heap
Am Anfang steht das Array A[1..n], das sortiert werden soll. Dieses Array ist auch gleichzeitig der Ort, an dem der Heap aufgebaut wird. Die folgende Illustration zeigt, wie man den linksvollständigen Binärbaum zum Array darstellen würde:
__ A[1]_
/ \
A[2] A[3]
/ \ / \
A[4] A[5] A[6] A[7]
/ \
A[8] A[9]
Ich denke, man kann spätestens ab hier gut erkennen, was genau ein linksvollständiger Binärbaum ist und warum man ihn in einem einfachen Array speichern kann, und warum das hier so passiert.
Aus allen genannten Eigenschaften kann man ableiten, dass Eigenschaft 3 für alle Elemente ab |_ n/2 + 1 _| auf jeden Fall erfüllt ist. Um nun den Heap aufzubauen, geht man also von diesem schon fertigen Teil aus und arbeitet sich rückwärts in den potenziell noch nicht stimmenden Teil, nämlich die erste Hälfte des Arrays, vor. Stößt man dabei auf einen Eintrag, der nicht stimmt, wird der mit dem größeren seiner beiden Kinder vertauscht. Dann muss natürlich noch sichergestellt werden, dass der Knoten an dieser Stelle nun endgültig richtig aufgehoben ist und größer ist als seine beiden neuen Kinder. Wenn das nicht der Fall ist, muss nochmal getauscht werden. Das passiert solange, bis alles sitzt; danach wendet man sich dem nächsten Feld beim rückwärts-durcharbeiten zu.
Dann hat man einen wunderschönen Heap vor sich, das erste Element ist tatsächlich das größste Element des ganzen Arrays. Und jetzt?
Die Sortierphase
Es geht endlich los! Man arbeitet sich jetzt wieder rückwärts durch das Array. Nach und nach wird jedes Element mit dem ersten (höchsten) vertauscht, so dass das höchste Element des Heaps am Ende des Arrays landet, und zwar genau da, wo es in der sortierten Reihenfolge hingehört. Nach einem solchen Tausch stimmt natürlich das erste Element des Heaps nicht mehr, und es muss wieder munter herumgetauscht werden, und zwar genau so, wie es schon beim Aufbauen gemacht wurde.
Das Beispiel
Praktischerweise habe ich ein kleines Perl-Script programmiert, das HeapSort schön bunt demonstriert. Und du kannst es hier live testen! Angezeigt werden nicht nur ein paar Statistiken zur Anzahl der benötigten Vergleiche und Vertauschungen, sondern auch der Zustand des Arrays nach jedem Schritt (der rot eingefärbte Teil ist der Heap).
start: a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 step 1: generating heap... ( 1a, 3c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 1a, 4c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 1a, 4c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 1a, 4c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 1a, 4c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 1a, 4c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 1a, 4c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 1a, 4c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 1a, 4c) a b c d e f g E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 2a, 8c) a b g d e f c E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 2a, 8c) a e g d b f c E X A M P L E 5 7 3 2 4 7 1 2 3 8 ( 3a, 12c) g e f d b a c E X A M P L E 5 7 3 2 4 7 1 2 3 8 step 2: sorting... ( 7a, 14c) f e c d b a E E X A M P L 8 5 7 3 2 4 7 1 2 3 g ( 8a, 18c) e d c X b a E E 4 A M P L 8 5 7 3 2 3 7 1 2 f g ( 7a, 14c) d b c X M a E E 4 A 2 P L 8 5 7 3 2 3 7 1 e f g ( 7a, 14c) c b a X M P E E 4 A 2 1 L 8 5 7 3 2 3 7 d e f g ( 7a, 17c) b X a E M P E 7 4 A 2 1 L 8 5 7 3 2 3 c d e f g ( 7a, 14c) a X P E M L E 7 4 A 2 1 3 8 5 7 3 2 b c d e f g ( 7a, 14c) X M P E A L E 7 4 2 2 1 3 8 5 7 3 a b c d e f g ( 6a, 13c) P M L E A 3 E 7 4 2 2 1 3 8 5 7 X a b c d e f g ( 6a, 13c) M E L 7 A 3 E 7 4 2 2 1 3 8 5 P X a b c d e f g ( 7a, 13c) L E E 7 A 3 8 7 4 2 2 1 3 5 M P X a b c d e f g ( 6a, 13c) E A E 7 5 3 8 7 4 2 2 1 3 L M P X a b c d e f g ( 6a, 10c) E A 8 7 5 3 3 7 4 2 2 1 E L M P X a b c d e f g ( 7a, 14c) A 7 8 7 5 3 3 1 4 2 2 E E L M P X a b c d e f g ( 6a, 10c) 8 7 3 7 5 2 3 1 4 2 A E E L M P X a b c d e f g ( 7a, 14c) 7 7 3 4 5 2 3 1 2 8 A E E L M P X a b c d e f g ( 6a, 10c) 7 5 3 4 2 2 3 1 7 8 A E E L M P X a b c d e f g ( 6a, 10c) 5 4 3 1 2 2 3 7 7 8 A E E L M P X a b c d e f g ( 5a, 9c) 4 3 3 1 2 2 5 7 7 8 A E E L M P X a b c d e f g ( 5a, 9c) 3 2 3 1 2 4 5 7 7 8 A E E L M P X a b c d e f g ( 5a, 6c) 3 2 2 1 3 4 5 7 7 8 A E E L M P X a b c d e f g ( 5a, 6c) 2 1 2 3 3 4 5 7 7 8 A E E L M P X a b c d e f g ( 4a, 4c) 2 1 2 3 3 4 5 7 7 8 A E E L M P X a b c d e f g ( 4a, 2c) 1 2 2 3 3 4 5 7 7 8 A E E L M P X a b c d e f g 157a (=> 52s), 361c total. explanation: a = assigns, s = swaps, c = compares, heap
Und weil ich so ein netter Mensch bin, kriegst du sogar noch besagtes
Perl-Script zusammen mit ein paar anderen Scripts, die andere
Sortieralgorithmen visuell darstellen, zum Auseinandernehmen und
Rumschrauben, veröffentlicht unter den Bedingungen der BSD-Lizenz.
» Download
Dieser Artikel wurde zuletzt am 21.12.2004 geändert.
Kommentare
- 19.09.2003 19:57, AC:Copyright © Jan 'jast' Krüger, 2003-2006. (Kontakt, OpenPGP Key)