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: