// 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 >= 0; i--) {
vertausche(a, 1, i); // vertausche 1. mit letztem unsortierten Element
versickere(a, i-1, 1); // stelle Heap-Eigenschaften für Rest-Array her
}
}
