HeapSort basiert, wie der Name bereits impliziert
auf der Datenstruktur des Heaps. Man unterscheidet Min-Heaps und Max-Heaps.
In einem Max-Heap steht das größte Element in der
Wurzel, bei einem Min-Heap steht dann logischerweise das kleinste Element in der
Wurzel.
Definition eines Max-Heaps:
Eine Folge F= k1,k2,...,
kN von Schlüsseln nennen wir einen Heap, wenn ki £
këi/2û für
2£
i £
N gilt. Anders ausgedrückt ki ³
k2i und ki ³
k2i+1, sofern 2i £
N bzw. 2i +1 £
N.
Aus der Definition geht hervor, dass die Element
2i und 2i+1 falls vorhanden, die Kinder des Knoten i sind. Dies kann man anhand
einer Baumsdarstellung gut erkennen.
Bsp.: Betrachten wir als Beispiel die Folge
F = 8,6,7,3,4,5,2,1.
Programm intern wird die Folge in einem Array
gespeichert, um die Vorgehensweise von HeapSort aber auch die eigentliche
Struktur zu erkennen, bietet sich eine Baumdarstellung des Heaps an.
Das
Aufbauen eines Heaps (Aufbauphase):
In
der Regel entsprechen beliebige Folgen nicht der Heap-Bedingung. Daher muss man
sie zunächst in einen Heap umwandeln um HeapSort auf sie anwenden zu können.
Dazu bedient man sich folgender Methode:
Eine Folge F= k1,k2,..., kN
von N Schlüsseln wird in einen Heap umgewandelt, indem die Schlüssel
kën/2û,
kën/2û-1,
..., k1 (in dieser Reihenfolge) in F versickern.
Betrachten wir dazu wieder ein Beispiel:
Sei F=2,1,5,3,4,8,7,6 die zu sortierende Folge. Die
Umwandlung der Folge in einen Heap vollzieht sich dann wie in folgender Zeichnung
dargestellt.
Das
Sortieren im Heap (Selektionsphase)
Ist die Struktur des Heaps erst mal hergestellt, so
ist das sortieren einfach.
Da im Max-Heap das
Maximum der Folge an der Wurzel steht, können wir das erste Element schon
sofort ablesen. Um die weiteren Elemente zu bestimmen, entfernen wir das Maximum
aus der Wurzel und tauschen es mit dem im Array am weitesten rechtsstehenden,
nicht sortiertem Element aus (Im Baum also dem auf der jeweilig letzen Ebene am
weitesten rechts, also das Element mit dem größten Index).
Durch
das Vertauschen der Schlüssel ist die Heap-Eigenschaft möglicherweise zerstört.
Hier liegt auch der schwierige Teil, nämlich das Wiederherstellen des Heaps.
Um
erneut einen Heap herzustellen nutzen wir die Tatsache aus, dass nach dem
Tauschen/Entfernen der Wurzel noch zwei TeilHeaps vorliegen.
Analyse:
Die Aufbauphase des Heaps hat Laufzeit O(n), also lineare
Laufzeit.
Warum:
O(Sh=1,log
n h * Anzahl der Knoten auf Höhe
h ) ; Anzahl der Knoten auf Höhe h £
n/2h
= O(Sh=1,log
n h
* n/2h )
-->
O(n*Sh=0,∞
h
/2h )= O(n)
Die
Selektionsphase des Heaps hat die Laufzeit O(n log n).
Warum:
Für r= n,...,n-1,...,1:
Lasse Wurzel s[1] sinken. Dies hat jeweils die Kosten O(Höhe(1) im
Heap S[1...r]) = O(log r)
-->
Gesamtkosten= O(Sr=1,n
log r )£
O(Sr=1,n
log n ) = O(n log n)
Ein vollständiger binärer Baum mit n Knoten hat die Tiefe
d<= log(n). Die Prozedur downheap benötigt daher höchstens
log(n) Schritte. Die Prozedur buildheap ruft für jeden Knoten
einmal downheap auf, benötigt also insgesamt höchstens n·log(n)
Schritte. Prozedur heapsort schließlich ruft einmal buildheap auf
und ruft anschließend für jeden Knoten einmal downheap auf, benötigt
also höchstens 2·n·log(n) Schritte.
Fazit
- HeapSort
liegt sowohl im Worstcase als auch im AverageCase in n log n.
- Der
Sortieralgorithmus ist ein In-Place Algorithmus.
- Vorsortierung
schadet nicht, kann sogar ausgenutzt werden.
- Iterativer
Algorithmus
|