20.05.2012
Liste von weiteren Sortierverfahren
Englische Version

Heap Sort

HeapSort ist ein sehr effizienter vergleichsbasiertes Sortierverfahren 1964 entwickelt von Robert W. Floyd und J. W. J. Williams. Es ist eine Weiterentwicklung vom SelectionSort und ist mit einer Worst Case Laufzeit von O(n log n) einer der besten vergleichsbasierten Sortieralgorithmen. Es arbeitet in-place, sortiert aber nicht stabil

  • sehr effizient mit fast allen Datensätzen
  • oft in der Prexis eingesetzt
  • in-place (bzw. in-situ, d.h. es wird kein zusätzlicher Speicher benötigt)

Idee

HeapSort benutzt, wie der Name schon erahnen lässt, eine Heap Datenstruktur. In der einfachsten Ausführung werden die Elemente der zu sortierenden Folge nacheinander in einen Min-Heap eingefügt. Die Datenstruktur kümmert sich um die Anordnung der Elementen in einem partiell geordneten Baum, sodass man schnell das Minimum entfernen kann. Tut man dies bis der Heap leer ist, so erhält man die Elemente in der richtigen Reihenfolge als sortierte Folge. Leider ist dies kein in-place Verfahren.

Um eine in-place Methode zu erreichen behilft man sich einem Trick: Aus dem zu sortierenden Array wird ein binärer Max-Heap in linearer Repräsentation konstruiert. Die zweite Hälfte des Arrays ist bereits ein Teilheap, da die Elemente alle Blätter sind. Jedes Element aus der ersten Hälfte wird nun nacheinander in diesen Teilheap nach unten wandern ("versickern"). Somit vergrößert sich der Heap um eins bis die gesamte Folge zum Heap umgewandlet wurde. Nun kann das Maximum entnommen werden und ans Ende des Heaps angehangen werden. Auf diese Weise wird das Array zweigeteilt: Am Anfang der Heap mit den verbleibenden zu sortierenden Elementen und am Ende die bereits sortierte Folge. Dies wird wiederholt bis der Heap leer und die gesamte Folge folglich sortiert ist.

Applet

© Miao Wang 2006 (Bug-Meldungen bitte an Webmaster@Wanginator.de richten)

Das Applet (benötigt Java) visualisiert einen einfachen HeapSort auf maximal 16 Elemente. Die Elemente der zu sortierenden Folge werden nacheinander in eine Heapstruktur (schwarz) eingefügt. Nachdem der Heap fertig gestellt ist, wird stets das Minimum entnommen und an die sortierte Folge angehangen bis der Heap leer und die Folge sortiert ist. Mit Insert lassen sich Werte zur Folge hinzufügen, mit Random Fill erhält man eine zufällige volle Folge generiert und mit Clear löscht man die aktuelle Folge. Mit einem Klick auf Sort wird stets ein Schritt des Verfahrens visualisiert.

Quellcode (Java)

Java Code:
Syntax Highlightning by Beautifier
public class HeapSort { public static void heapsort(int[] a) { //Heap Struktur errichten buildheap(a); //Maximum entnehmen extract(a); } private static void buildheap(int[] a) { //den Heap von halber Größe auf gesamte Größe wachsen lassen for(int i=a.length/2-1; i>=0; i--) { heapify(a,i,a.length); } } private static void extract(int[] a) { int n = a.length; //n trennt den Heap von der sortierten Folge while (n>1) { n--; //das Maxmimum ans Ende des Heap bringen swap(a,0,n); //Heap-Invariante wiederherstellen heapify(a,0,n); } } //Heap-Invariante wiederherstellen private static void heapify(int[] a, int i, int n) { int k=2*i+1; //erstes Kind von i while (k<n) { //falls weiteres Kind existiert und das Kind das Maximum ist if (k+1<n && a[k+1]>a[k]) k++; if (a[i]>=a[k]) { return; //Heap-Invariante wiederhergestellt } else { //vertausche Element mit seinem Kind swap(a, i, k); //fahre mit nächster Iteration fort i=k; k=2*i+1; } } } private static void swap (int[] a, int i, int j) { int h = a[i]; a[i] = a[j]; a[j] = h; } }

Varianten

Bottom-Up HeapSort ist eine Variante von Ingo Wegener aus dem Jahre 1990, der den Aufwand der Vergleiche für größere Datenmengen verringert. Ein Element, welches in den Heap "versickern" muss, wird nicht schrittweise durchgeführt, sondern "versickert" direkt zur Blattebene und korrigiert dies, indem es wieder nach oben wandert. Da in großen Datenmengen die Wahrscheinlichkeit groß ist, dass Elemente im unteren Teil des Heaps sich wiederfinden, bringt dies Vorteile. Für kleinere Datenmengen ist eine normale Heap-Variante vorzuziehen.

HeapSort hat keine Vorteile gegenüber einfacheren Verfahren, wenn es um eine bereits sortierte Folge handelt. Elemente dieser Folge müssten im Heap nach oben wandern, um als Maximum wieder nach hinten plaziert zu werden. Um dies zu verhindern, veröffentlichte Edsger W. Dijkstra 1981 SmoothSort als Variante von HeapSort. Es verbessert den Best Case bei einer bereits sortierten Folge auf O(n). Jedoch muss dafür der Heap verkehrt herum implementiert werden und bringt einen gewissen Aufwand mit sich. Da der Average und Worst Case nicht verbessert werden, lohnt sich SmoothSort in der Regel nicht. [4]

Je mehr Elemente zu sortieren sind, desto vorteilhafter wäre es eine flachere Baumstruktur zu haben. Deshalb kann es in manchen Fällen nützlich sein den Grad des Heaps anzupassen, z.B. ternäre oder gar n-äre Heaps statt binäre.

Analyse

Ein HeapSort, der nicht in-place arbeitet, benötigt n mal O(log n) zum Erstellen des Heaps und erneut n mal O(log n) um die Minima zu entnehmen. Das Resultat ist eine Laufzeit von O(n log n). Bei der in-place Variante wird nur O(n) gebraucht um den Heap zu erstellen, aber immer noch n mal O(log n) um die Maxmima zu entnehmen. Daher belibt die Laufzeit bei O(n log n). Verglichen mit QuickSort jedoch, garantiert HeapSort eine Laufzeit von O(n log n) und kennt keinen Worst-Case.

Weiterführende Links und Literatur

Last Update: 05.04.2011 02:46:53
Valid XHTML 1.0 Transitional!Valid CSS!