Heapsort

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 einen 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 Max-Heap

Datei:Binärbaum.png

Repräsentation des Arrays [H|E|A|P|S|O|R|T] als Binärbaum

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

Man möchte ein Array mit dem Inhalt [H|E|A|P|S|O|R|T] in einen Max-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 ist, tauschen wir beide.
H E A T S O R P    Wir fahren mit dem A fort. Seine Nachfolger sind
    ^     ^ ^      O und R. Es gilt sowohl R>O als auch 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.
  ^   ^ ^          Es gilt 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 Max-Heap überführt.

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 liegt bereits
^           ^       jenseits des Heaps im fertig sortierten Bereich.
                    Wir haben also wieder einen korrekten Heap und können
                    S und A vertauschen, womit auch das S sortiert ist.
A P R E H O|S T     Jetzt müssen wir das A versickern.
^ ^ ^               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 ist 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 versickern 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

Java

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

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

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

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

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)).

Für genügend große n (>16000) ist ein Heapsort im Durchschnitt schneller als ein optimierter Quicksort. Hinzu kommt das bessere Worst-Case-Verhalten von O(n·log(n)) gegenüber O(n²) beim Quicksort, so dass bei großen Sortiermengen Heapsort zu bevorzugen ist.

Varianten

Bottom-Up-Heapsort

Eine Variante des Heapsort-Algorithmus ist das Bottom-Up-Heapsort, das häufig fast die Hälfte der nötigen Vergleichsoperationen einsparen kann und sich folglich besonders da rentiert, wo Vergleiche aufwändig sind.

Smoothsort

Normales Heapsort sortiert bereits weitgehend vorsortierte Felder nicht schneller als andere. Die größten Elemente müssen immer erst ganz nach vorn an die Spitze des Heaps wandern, bevor sie wieder nach hinten kopiert werden. Smoothsort ändert das, indem es im Prinzip die Reihenfolge des Heaps umdreht. Dabei ist allerdings beträchtlicher Aufwand nötig, um den Heapstatus beim Sortieren aufrecht zu erhalten.

Ternäre Heaps

Eine andere Optimierung verwendet statt binären ternäre Heaps. Diese Heaps beruhen statt auf Binärbäumen auf Bäumen, bei denen jeder vollständig besetzte Knoten 3 Kinder hat. Damit kann die Zahl der Vergleichsoperationen um etwa 3–4 % reduziert werden (bei einigen Tausend bis einigen Millionen Elementen). Außerdem sinkt der sonstige Aufwand deutlich; insbesondere müssen durch den flacheren Heap knapp ein Drittel weniger Elemente beim Versickern verschoben werden.

In einem binären Heap kann ein Element mit 2n Vergleichen um n Ebenen abgesenkt werden und hat dabei durchschnittlich 3/2·(2ⁿ-1) Indizes übersprungen. In einem ternären Heap kann ein Element mit 3m Vergleichen um m Ebenen abgesenkt werden und hat dabei durchschnittlich 3^m-1 Indizes übersprungen. Wenn bei gleicher Reichweite der relative Aufwand x := 3m/2n ist, dann gilt

${\frac {3}{2}}\left(2^{n}-1\right)=3^{{\frac {2n}{3}}x}-1$, also$x={\frac {3}{2n}}\log _{3}\left({\frac {3}{2}}2^{n}-{\frac {1}{2}}\right)=_{n\to \infty }{\frac {3}{2}}\log _{3}2\approx 0{,}946$

Bei n=18 (realistisch bei knapp 1 Million Elementen) ergibt sich 0,977; die 1 wird oberhalb von n=10 unterschritten. In der Praxis ist die Ersparnis etwas größer, u.a. deswegen, weil ternäre Bäume mehr Blätter haben und deshalb beim Aufbau des Heaps weniger Elemente versickert werden müssen.

Insgesamt kann die Sortierung mit ternären Heaps bei großen Feldern (mehrere Millionen Elemente) und einfacher Vergleichsoperation 20–30 % Zeit einsparen. Bei kleinen Feldern (bis etwa tausend Elemente) lohnen sich ternäre Heaps nicht oder sind sogar langsamer.

n-äre Heaps

Bei noch breiteren Bäumen bzw. flacheren Heaps steigt die Zahl der nötigen Vergleichsoperationen wieder an. Trotzdem können sie vorteilhaft sein, weil der sonstige Aufwand (vor allem der für das Kopieren von Elementen) weiter sinkt und geordneter auf die Elemente zugegriffen wird, was die Effizienz von Caches erhöhen kann. Sofern bei großen Feldern nur ein einfacher numerischer Vergleich durchzuführen ist und Schreiboperationen relativ langsam sind, können 8 oder mehr Kinder pro Knoten optimal sein.

Einfache Beispielsimplementierung mit Heaps beliebiger Arität (ab 2) in C99:

int heapsort( int * data, int n )    // zu sortierendes Feld und seine Länge
{
  const int WIDTH= 8;                // Anzahl der Kinder pro Knoten
  int val, parent, child, w, max, i;
  int m= (n + (WIDTH - 2)) / WIDTH;  // erstes Blatt im Baum
  int count= 0;                      // Zähler für Anzahl der Vergleiche

  for ( ; ; )
  {
    if ( m ) {                       // Teil 1: Konstruktion des Heaps
      parent= --m;
      val= data[parent];             // zu versickernder Wert
    }
    else
    if ( --n ) {                     // Teil 2: eigentliche Sortierung
      val= data[n];                  // zu versickernder Wert vom Heap-Ende
      data[n]= data[0];              // Spitze des Heaps hinter den Heap in
      parent= 0;                     //   den sortierten Bereich verschieben
    }
    else                             // Heap ist leer; Sortierung beendet
      break;

    while ( (child= parent * WIDTH + 1) < n )  // erstes Kind;
    {                                          // Abbruch am Ende des Heaps
      w= n - child < WIDTH ?
         n - child : WIDTH;          // Anzahl der vorhandenen Geschwister

      count += w;

      for ( max= 0, i= 1; i < w; ++i )         // größtes Kind suchen
        if ( data[child+i] > data[child+max] )
          max= i;

      child += max;

      if ( data[child] <= val )      // kein Kind mehr größer als der
        break;                       //   zu versickernde Wert

      data[parent]= data[child];     // größtes Kind nach oben rücken
      parent= child;                 // in der Ebene darunter weitersuchen
    }

    data[parent]= val;               // versickerten Wert eintragen
  }

  return count;
}

Zu Vergleichszwecken gibt die Funktion die Anzahl der durchgeführten Vergleiche zurück.

Weblinks

• Robert F. Stärk: Animated Sorting Algorithms - Java-Beispiele
• VisuSort Framework - Visualisierung diverser Sortieralgorithmen (Windows)
• Sortierung - Algorithmen und Visualisierung
• Java-Applet zur Demonstration
• Weiteres Java-Applet
• Noch ein weiteres Java-Applet zur Demonstration