public class HeapSort {
    // Versickere das Element mit Index zuversickern in dem Teilfeld von Index
    // links bis einschließlich Index rechts
    public static void versickere(int[] array, int zuversickern, int links, int rechts) {
        // TODO: Praktikum 9
        int i = links;
        int j = 0;
//      boolean versickernErforderlich = true;
        while (2 * i <= rechts) { // linkes Kind vorhanden
            j = 2 * i;
            if (j + 1 <= rechts && array[j] < array[j + 1]) // wenn rechtes kind vorhanden UND größer als linkes
                j++; // j = rechtes Kind
            // j ist jetzt das größte Kind
            if (zuversickern < array[j]) { // Wenn Knoten kleiner als größtes Kind
                array[i] = array[j]; // größtes Kind steigt auf Elternposition
                i = j; // zu versickernder Knoten jetzt an Stelle des größten Kindes
            } else {
                array[i] = zuversickern;
                break;
//              i = rechts;
//              versickernErforderlich = false; // Bereits an Zielposition. Versickern nicht weiter nötig
            }
        }
//      if (versickernErforderlich)
//          array[i] = zuversickern;
    }

    public static void heapsort(int[] array, int links, int rechts) {
        // TODO: Praktikum 9

        // Array in Heap umwandeln
        for(int i = (links + rechts + 1) / 2 - 1; i >= links; i--){
            versickere(array, array[i], i, rechts); // startet versickern bei Knoten i
        }

        int hilf = 0;
        for(int i = rechts; i > links; i--){
            hilf = array[links];
            array[links] = array[i];
            array[i] = hilf;
            versickere(array, array[links], links, i-1); // sortierter bereich nicht übergeben
        }
    }
}