Heapsort

Inhaltsverzeichnis

1 Heaps 2 Beispiel für die Überführung in einen 3 Prinzip der Sortierung 4 Beispiel für die Sortierung 5 Implementierung 6 Varianten 7 Laufzeit

Heaps

Um ein Array in einen Heap überführen beginnt man deshalb in der Mitte Arrays. Man "versickert" nun sukzessive alle davor Knoten bis das erste Element versickert wurde. Versickern heißt dass man einen Knoten mit größeren seiner beiden Nachfolgeknoten vertauscht falls dieser ist als er selbst und damit so fortfährt bis er keinen Nachfolgeknoten mehr hat größer ist als er selbst.

Um die Rechnung zu vereinfachen wird Folgenden vorausgesetzt dass das erste Element des den Index 1 hat. Die Nachfolger eines mit dem Index i liegen dann an Positionen 2·i und 2·i+1.

Beispiel für die Überführung in einen

Man möchte ein Array mit dem [H|E|A|P|S|O|R|T] in einen Heap überführen wobei gilt:

  1 2 3 4 5 6 7  H E A P S O T Wir beginnen links von der Mitte bei P: ^ ^ sein Nachfolger ist Da T>P tauschen wir beide. H E T S O R P Wir fahren dem A fort. Seine Nachfolger sind ^ ^ O und R. R>O und R>A. tauschen wir R und A. H E T S O A P Dann vergleichen E mit seinen Nachfolgern T und S. ^ ^ T>S und T>E. Deshalb müssen T und E vertauschen. H T R S O A P Wir müssen nun weiter versickern denn der neue ^ ^ von E ist P und P>E. H R P S O A E Nun wir H mit seinen ^ ^ ^ T und R. T>R und T>H. T R P S O A E Wir das H weiter. ^ ^ ^ S>P S>H. T S R P H O E Wir haben das Array nun in Heap überführt.  

Prinzip der Sortierung

Der eigentliche Sortieralgorithmus nutzt die Tatsache dass die Wurzel eines Heaps stets der größte Knoten Da im fertig sortierten Array der größte ganz rechts stehen soll vertauscht man das mit dem letzten Arrayelement.

Das Element am Ende des Arrays nun an der gewünschten Position und bleibt Den Rest des Arrays muss man wieder einen Heap überführen indem man das erste versickert.

Anschließend vertauscht man das erste mit vorletzten Element d.h. die beiden größten Werte wie gewünscht am Ende des Arrays. Man das nun erste Element usw.

Beispiel für die Sortierung

Wir sortieren den oben erhaltenen Heap

  1 2 3 4 5 6 7  T S R P H O E Wir vertauschen das erste Element mit letzten. ^ ^ E S R P O A|T Das T ist nun an korrekten Position. ^ ^ ^ Nun müssen das E versickern. S>R und S>E S R P H O A|T P>H und ^ ^ ^ S P R E O A|T Wir versickern E nicht weiter T ist bereits an der ^ ^ Position. Stattdessen vertauschen wir S und A. P R E H O|S T Jetzt wir das A. ^ ^ ^ R>P R>A. R P A E H O|S Da das S bereits korrekt liegt vergleichen ^ ^ nur A und O. O>A. P O E H A|S T Die für das linke Teilarray sind wieder ^ erfüllt. Wir vertauschen R und A. A O E H|R S T Wir versickern ^ ^ ^ P>O und P>A. P O E H|R S T Wir versickern weiter. H>E und H>A. ^ ^ ^ H O E A|R S T Wir P und A. ^ ^ A H E|P R S T Wir versickern A. ^ ^ O>H und O>A. O H E|P R S T Wir vertauschen O E. ^ ^ E H A|O P S T Wir versickeren E. ^ ^ H>A und H>E. H E A|O P S T Wir vertauschen H und A. ^ A E|H O P R S Wir versickern A. E>A. ^ ^ E O P R S T Wir vertauschen und A. ^ ^ A|E H O R S T Das Array ist jetzt sortiert.  

Implementierung

Hier eine Implementierung von HeapSort in Java mit der man allerdings statt Buchstaben Zahlen sortiert:

 // vertauscht in einem Array die mit Index x und y private static vertausche(int[] array int x int y){ int zwischenspeicher = array[x]; array[x] = array[y]; array[y] zwischenspeicher; }  

 // versickert im Array mit Länge das Element mit Index  index  private static void versickere(int[] array int int index){ while (index <= n/2){ int = 2*index; //linker Nachfolger if (nachfolger < // hat der Knoten einen rechten Nachfolger if (array[nachfolger+1]>array[nachfolger]) // ist der größer als linke? nachfolger++; //dann benutze den rechten sonst linken Nachfolger if (array[nachfolger] > array[index]){ vertausche(array nachfolger); // vertausche mit größerem Nachfolger index=nachfolger; versickere weiter } else{ // beide Nachfolger kleiner als das Element kann nicht index=n; weiter versickern: beende Schleife } } } 

 // überführt ein Array in einen private static void überführeInHeap(int[] array int n){ (int index=n/2; index>=1; index--){ // starte von Mitte aus rückwärts versickere(array n index); }  

 // sortiert ein Array von ganzen public static void heapSort(int[] array int n){ n); // stelle Heap-Eigenschaft her for (int index>=1; index--){ vertausche(array 1 index); // vertausche mit letztem unsortierten Element versickere(array index-1 1); stelle Heap-Eigenschaften für Rest-Array her } } 

Varianten

Eine Variante des HeapSort-Algorithmus ist das Theoretisch könnte man HeapSort auch mit ternären implementieren dies ist aber relativ kompliziert und keine entscheidenden Geschwindigkeitsvorteile.

Laufzeit

Bücher zum Thema Heapsort

Dieser Artikel von Wikipedia unterliegt der GNU FDL.