AdViews-Sponsor Werbepartner
WebSite Vermarktung


Navigation-Bar

 
Home
Tutorials
Links
Downloads
Seminare
Impressum


Seminare

 
ePayment
Wissensmanag.
Informationsman.
SmartCards
mCommerce
PKI
ASP


 

HeapSort

 

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.

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

 



Skripte Top 5

 
  Bubblesort
  Heapsort
  .htaccess
  Mergesort
  Quicksort


Der Klassiker

 
 
Im Eishaus


 

   Home | Tutorials | Links | Downloads | Seminare | Impressum  

All Rights reserved by Greenbutter.de, 2000,2001