HeapSort ist ein 1964 von Robert W. Floyd und J.W.J. Williams entwickeltes, relativ schnelles Sortierverfahren. Es handelt sich um eine Verbesserung von SelectionSort. Seine Komplexität ist bei einem Array der Länge n in der Landau-Notation ausgedrückt O(n·log(n)). HeapSort arbeitet zwar in-place, ist jedoch nicht stabil.

Heaps

Die Voraussetzung dafür, dass man ein Array von sortierbaren Werten mit HeapSort sortieren kann, ist, dass dieses einen binären Heap repräsentiert. Ist dies nicht der Fall, so muss man es zuerst in ein Heap überführen.

Man beachte, dass für die zweite Hälfte jedes Arrays die Heap-Eigenschaft bereits erfüllt ist, denn jeder Knoten in der zweiten Hälfte des Arrays entspricht im Heap einem Blatt, hat also keinen Nachfolgeknoten, dessen Wert größer sein könnte als der eigene (Im Folgenden wird der Einfachheit halber der Knoten mit dem größten Wert der "größte Knoten" genannt).

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

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

Beispiel für die Überführung in einen Heap

Man möchte ein Array mit dem Inhalt [H|E|A|P|S|O|R|T] in einen Heap überführen, wobei gilt: A<B<C<...<Y<Z.

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

In einen Heap überführter Binärbaum, entspricht [T|S|R|P|H|O|A|E]

Prinzip der Sortierung

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

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

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

Beispiel für die Sortierung

Wir sortieren den oben erhaltenen Heap [T|S|R|P|H|O|A|E].

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

Implementierung

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

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

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

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

// sortiert ein Array von ganzen Zahlen
public static void heapSort(int[] array, int n){
  überführeInHeap(array, n);    // stelle Heap-Eigenschaft her
  for (int index=n; index>=1; index--){
    vertausche(array, 1, index); // vertausche 1. 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 BottomUp-HeapSort. Theoretisch könnte man HeapSort auch mit ternären Heaps implementieren, dies ist aber relativ kompliziert und bringt keine entscheidenden Geschwindigkeitsvorteile.

Laufzeit

Man kann zeigen, dass der Aufbau des Heaps, in Landau-Notation ausgedrückt, in O(n) Schritten ablaufen kann. Das Versickern eines Elements von der Wurzel benötigt im ungünstigsten Fall (worst case) O(log(n)) Schritte. Insgesamt garantiert HeapSort eine Laufzeit von O(n·log(n)).

Weblinks

• http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html Java Beispiele (http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html)
• http://www.rhirte.de/vb/sort.htm Visualisierung der Algorithmen (http://www.rhirte.de/vb/sort.htm)