HeapSort für Array of Strings funktioniert nur teilweise

[Balunal]

Hallo,
Ich habe als Aufgabe eine HeapSort Variante zu implementieren, die Strings aufsteigend sortiert. Ich habe mich daran versucht, der Sortieralgorithmus funktioniert jedoch nur teilweise. Wenn es maximal 11 Elemente sind gibt es kein Problem, danach werden nur die ersten 6 und die letzten 5 Elemente sortiert. Würde mich freuen wenn Ich diesbezüglich Hilfe bekommen könnte, gerne auch ein völlig anderer Lösungsansatz.
Mfg

PS:
Die Ausgabe der main wäre hier:
a b c d e f i h g j k l m n

[/B]
public class HeapSort {

    static int idx = -1;
    static String []heap = new String[1000];
    static void heapForm(String k){
        idx++;
        heap[idx] = k;
        int child = idx;
        String tmp;
        int index = idx / 2;

        while (index >= 0){
            if (heap[index].compareTo(heap[child]) > 0){
                tmp = heap[index];
                heap[index] = heap[child];
                heap[child] = tmp;
                child = index;

                index = index / 2;
            }
            else{
                break;
            }
        }
    }


    static void heapSort() {
        int left1, right1;

        while (idx >= 0) {
            String k;
            k = heap[0];

            System.out.print(k + " ");

            heap[0] = heap[idx];

            idx = idx - 1;
            String tmp;
            int index = 0;
            int length = idx;

            left1 = 1;
            right1 = left1 + 1;

            while (left1 <= length) {

                if (heap[index].compareTo(heap[left1]) <= 0 &&
                        heap[index].compareTo(heap[right1]) <= 0){
                    break;
                }


                else {
                    if (heap[left1].compareTo(heap[right1])< 0){
                        tmp = heap[index];
                        heap[index] = heap[left1];
                        heap[left1] = tmp;
                        index = left1;
                    }

                    else {
                        tmp = heap[index];
                        heap[index] = heap[right1];
                        heap[right1] = tmp;
                        index = right1;
                    }
                }


                left1 = 2 * left1;
                right1 = left1 + 1;
            }
        }
    }

    static void sort(String k[], int n) {

        for (int i = 0; i < n; i++) {
            heapForm(k[i]);
        }
        heapSort();
    }

    public static void main(String[] args)
    {
        String arr[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n" };
        int n = arr.length;
        sort(arr, n);
    }
}

[B]

 

[Meniskusschaden]

Wenn du das letzte Heap-Element an die Wurzel geholt hast und es anschließend nach unten sinken lässt, berechnest du die Kindknoten auch dann aus dem linken Teilbaum, wenn es in den rechten Teilbaum ging.

 

[Balunal]

Wenn du das letzte Heap-Element an die Wurzel geholt hast und es anschließend nach unten sinken lässt, berechnest du die Kindknoten auch dann aus dem linken Teilbaum, wenn es in den rechten Teilbaum ging.

Aber warum tritt das dann erst ab 11 Elementen auf? Und wie würdest du vorschlagen das zu lösen? Bin etwas ideenlos im Moment und weiß nicht, ob Ich einfach etwas offensichtliches im Code übersehe oder etwas an HeapSort missverstanden habe.
Aber vielen Dank für die Antwort schonmal 😀

 

[Meniskusschaden]

Aber warum tritt das dann erst ab 11 Elementen auf?

Das liegt vermutlich an den Beispieldaten. Ich habe das nicht weiter untersucht, weil mir inzwischen weitere Fehler aufgefallen sind: Deine Berechnung der Kindknoten bzw. Elternknoten passt für ein Array mit Startindex 1. Du verwendest jedoch Startindex 0 und müsstest die Formeln deshalb entsprechend anpassen. Dadurch könnte derzeit schon beim Einfügen eines Elementes die Heap-Bedingung verletzt werden.

Und wie würdest du vorschlagen das zu lösen?

Ich habe in folgender Grafik mal ein Beispiel dargestellt. Beim Übergang vom vorletzten zum letzten Baum passiert der Fehler, weil du dort nicht mehr die Kinder der neuen Position von D untersuchst, sondern die linken Enkel der vorherigen Position von D. Das musst du ändern.