Heapsort

Grundlagen

Der Heapsort wurde von Robert W. Floyd und J. W. J Williams entwickelt. Er gehört zu den instabilen Sortieralgorithmen in der Informatik, arbeitet dabei aber nach dem in-place-Prinzip. Die Funktionsweise basiert eigentlich hauptsächlich auf binären Heap Eigenschaften als zentrale Datenstruktur und ist dabei ein fast vollständiger binärer Baum. Die Knoten enthalten dann die Daten, die wir letztendlich sortieren möchten. Wenn du nicht genau weißt, was ein Heap und ein Binärbaum genau sind, schau dir am besten zuerst unsere Videos dazu an.

direkt ins Video springen

Das Sortierverfahren hat eine Zeitkomplexität von O(n log(n)), damit gibt es keinen asymptotisch schnelleren Sortieralgorithmus der vergleichsbasiert ist. Man kann ihn im Allgemeinen durch seine Vorgehensweise auch als Verbesserung zum Selectionsort verstehen.

Heapsort Beispiel

Am besten wir schauen uns direkt ein Heapsort Beispiel an. Dafür nehmen wir einfach mal diese Liste, die wir von klein nach groß sortieren wollen – heißt also nach dem Max-Heap. Zuerst fangen wir damit an, dass wir die Zahlen in einer binären Baumstruktur anordnen. Wir starten also mit der ersten Zahl als Wurzel und arbeiten uns nach und nach bis zum letzten Element nach unten durch. Jetzt können wir mit dem Sortieren beginnen.

Buildheap

Dafür muss jeder Knoten die Heap-Bedingung – also die Heap Eigenschaft – erfüllen. Das bedeutet eigentlich nur, dass der sogenannte Vater immer größer als seine Kinder sein muss. Wir prüfen das Ganze von hinten nach vorne oder eben von den Blättern in Richtung Wurzel.

direkt ins Video springen

Wir betrachten also zuerst die untersten Zahlen. In unserem Fall haben wir die 8 als Vater und die Kinder 6 und 4. Beide sind kleiner, deswegen ändern wir hier erstmal nichts. Als nächstes schauen wir uns den Knoten 5 an. Die 7 ist größer und muss deshalb mit der 5 ausgetauscht werden. Im nächsten Schritt sehen wir uns die 9, 8 und 1 an, die Reihenfolge stimmt hier. Dann kommen wir beim letzten Knoten an. Hier muss die 9 mit der 2 vertauscht werden.

Downheap

Jetzt haben wir also einmal unseren Baum nach oben hin nach der Heap-Bedingung geordnet, aber durch den letzten Tausch, kann es immer sein, dass wir die vom Tausch betroffene Seite so beeinflusst haben, dass die Bedingungen in den unteren Reihen doch nicht mehr gegeben ist. Die 2 ist kleiner als die 8 und muss deshalb tatsächlich ausgetauscht werden. Genau dasselbe machen wir dann auch noch mit der 2 und der 6. Jetzt haben wir im gesamten Baum die Heapsort-Bedingung erfüllt. Nun kommen wir dann auch zum letzten Schritt, dabei tauschen wir einfach immer die aktuelle Zahl der Wurzel mit dem letzten Blatt aus – also die 9 mit der 4. Damit ist die 9 endgültig richtig sortiert und wir können sie im nächsten Durchlauf ignorieren.

Algorithmus

Welcher Algorithmus steckt nun genau hinter dem Heap Sort? Als erstes benötigen wir natürlich erstmal eine Liste, die nach dem Heap Sort geordnet werden soll, in unserem Fall nach dem Max-Heap – also von klein nach groß. Im nächsten Schritt muss also aus dem Array ein max-Heap gebaut werden (Build-Max-Heap). Dann kommt auch schon der Hauptteil, welcher unterschiedlich benannt werden kann. Du kennst ihn entweder unter dem Begriff Heapyfy, Downheap, Versickern oder eventuell auch Versenken. Diese Prozedur beschreibt die oben im Beispiel ausführlich erklärte Prüfung der Heap-Bedingung bezüglich der Kinder mit ihrem jeweiligen Vater. Wenn die Heap-Bedingung nicht erfüllt ist, muss das größere Kind mit dem Vater ausgetauscht werden. Dies wird so oft wiederholt, bis die Heap-Size 1 ist, also wir nur noch ein „unsortiertes“ Element haben.

Heapsort Pseudocode

Auf Basis des Algorithmus lässt sich ein Heapsort Pseudocode der einzelnen Prozeduren dann beispielsweise so darstellen:

Heapsort(arr) {
  BuildMaxHeap(arr)
  for i 
    tausche arr[1]  arr[i]
    heapsize 
    Versickern(arr, 1)
  }
  BuildMaxHeap(arr) {
    heapsize 
    for i 
      Versickern(arr, i)
    }
  Versickern(arr, i) {
    l 
    r 
    if (larr[i])
      largest 
    else
      largest 
    if (rarr[largest])
      largest 
    if (largest != i) {
      tausche arr[i]  arr[largest]
      Versickern(arr, largest)
    }
}

Heapsort Java – Implementierung

Hier kannst du dir einen beispielhaften Heapsort Java-Code ansehen, mit dem du den Algorithmus Stück für Stück mit den einzelnen Prozeduren implementieren kannst.

//Array der mit dem Heapsort sortiert werden soll
private static void heapSort(int[] arr) {
  BuildMaxHeap(arr);
  // Sortierung:
  for(int i = arr.length -1; i > 0; i–) {
    tausche(arr, i, 0);
    versickern(arr, 0, i);
  }
}
// Erstelle im Array einen MaxHeap Baum
private static void BuildMaxHeap(int[] arr) {
  for(int i = (arr.length / 2) – 1; i >= 0 ; i–) {
    versickern(arr, i, arr.length);
  }
}

// Versickern – Downheap
private static void versickern(int[] arr, int i, int j) {

while(i <= (j / 2) – 1) {

    // linkes Kind
    int kindIndex = ((i+1) * 2) – 1;
    // rechtes Kind
    if(kindIndex + 1 
      if(arr[kindIndex] 
        kindIndex++;
      }
    }
    // Test, ob Versickern notwendig ist
    if(arr[i] 
      tausche(arr,i,kindIndex);
      i = kindIndex;
    } else break;
  }
}
// Tauschen
private static void tausche(int[] arr, int i, int kindIndex) {
  int k = arr[i];
  arr[i] = arr[kindIndex];
  arr[kindIndex] = k;
}

Heapsort Komplexität

Die Heapsort Komplexität beträgt im Allgemeinen Vergleiche. Damit ist er bezüglich vergleichsbasierten-Sortieralgorithmen das schnellste asymptotische Sortierverfahren.  Jedoch kann er trotzdem beispielsweise mit dem Quicksort in seiner standardisierten Form nicht mithalten. Da der Heapsort in verschiedenen Prozeduren abläuft, kann für jedes eine eigene Laufzeitkomplexität festgestellt werden. Der downheap benötigt beispielsweise log(n) Schritte beim Vergleichen. Der buildheap zeigt bei einer genaueren Analyse auf, dass er nur Vergleiche braucht.

Wenn man sich die potentiellen Fälle genauer ansieht, kann gesagt werden, dass die Heapsort Laufzeit sowohl im Worst Case, als auch im Average Case und Best Case beträgt. Grund dafür ist, dass der Heap-Aufbau eine schrittweise vollständige Invertierung der Sortierreihenfolge benötigt.

Varianten

Für den Heapsort gibt es verschiedene Varianten. Neben dem Standard-Heapsort gibt es noch den Bottom-Up-Heapsort, den Smoothsort, die Ternären Heaps und die n-äre Heaps, welche die Komplexität in verschiedenen Bereichen potenziell steigern können.

Bottom-Up-Heapsort

Die dabei populärste Variante ist der Bottom-Up-Heapsort, da er oft nur die Hälfte an Vergleichsoperationen benötigt und kommt damit der Laufzeit des Quicksort sehr Nahe. Aber wie funktioniert das? Da ein Binärbaum größtenteils aus Blättern besteht und sich durch das Sortieren die niedrigeren Werte bereits abgesenkt werden mussten, arbeitet die Variante mit der Annahme, dass ein Element bis zur Blattebene oder in der Nähe versickert werden muss. Entsprechend wird auf Verdacht bis zur Blattebene abgesenkt und auf den zweiten Vergleich verzichtet. Der Bottom-Up-Heapsort sollte aber nicht bei kleineren Feldern mit einfacher numerischer Vergleichsoperation benutzt werden oder sehr viele Elemente gleichwertig sind. Heißt also, man sollte ihn vor allem bei großen Datenmengen mit hohem Aufwand pro Vergleichsoperationen verwenden.

Smoothsort

Der Smoothsort ändert die Reihenfolge der Vorgehensweise. Während normalerweise vorsortierte Felder keinen Vorteil erbringen, da immer das größte Element an die Wurzel wandern muss, um die Zahl anschließend wieder mit dem letzten Knoten austauscht, arbeitet der Smoothsort direkt umgekehrt. Jedoch ist bei der Umsetzung die Gewährleistung des Heapstatus beim Sortieren sehr aufwändig.

Ternäre Heaps

Wie man sich vielleicht schon denken kann, werden hier statt binären Heaps, ternäre Heaps benutzt. Entsprechend läuft er nicht auf Basis eines Binärbaums, sondern ein vollständig besetzter Knoten hat jeweils 3 Kinder. Dadurch können die Vergleichsoperationen reduziert werden. Beispielsweise bei sehr großen Feldern, die mehrere Millionen Elemente enthalten, kann dabei 20-30% der Vergleiche eingespart werden, wenn man sich das gleiche aber bei kleineren Feldern ansieht, kann es sogar sein, dass der Sortieralgorithmus dadurch langsamer als der Standard-Heapsort ist.

n-äre Heaps

Wie schon bei den Ternären Heaps, kann der Baum natürlich noch breiter, bzw. die Heaps noch flacher gestaltet werden, durch das Erweitern der Anzahl von Kindern eines Vaters. Dadurch steigt die Anzahl der Vergleichsoperationen zwar weiter an, jedoch können dadurch andere Vorteile bezüglich der Effizienz von Caches geschaffen werden, da der sonstige Aufwand weiter gesenkt werden kann und geordneter auf die Elemente zugegriffen werden kann.