Heap-Sort
aus www.iwiki.de, der freien Wissensdatenbank
Der Heap-Sort ist eine verbesserte Variante des Selection-Sort.
Inhaltsverzeichnis |
Voraussetzungen
Um den Heap-Sort anwenden zu können, muss das zu sortierende Array in Form eines binären Heaps vorliegen.
Funktionsweise
Die Wurzel des Heaps (im Array ganz links) repräsentiert generell den grössten Wert. Dieser soll im fertig sortieren Array ganz rechts stehen. Demnach wird er mit dem Element ganz rechts getauscht. Das letzte Element des Arrays ist nun also schon in der korrekten Position. Der Rest des Arrays muss nun abermals in einen Heap überführt werden, indem man das erste Element "versickert" (siehe Java-Implementierung). Nun vertauscht man abermals das erste mit dem vorletzten Element im Array. Anschliessend wird das erste Element wieder versickert, usw.
Animation
Java-Implementierung
// 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 i
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
}
}
