Was ist falsch an meinem HeapSort-Code?

Question

Ich versuche, eine Heapsort Methode in Java zu schreiben, aber es ist nicht genau das funktioniert, wie ich es will:

public class HeapSort { 

    private static int n; 

    private static void swap(int[] A, int a, int b) 
    { 
     int tmp = A[a]; 
     A[a] = A[b]; 
     A[b] = tmp; 
    } 

    private static void insert(int[] A, int i) 
    { 
     int left = i * 2; 
     int right = left + 1; 
     int max = i; 

     if (left <= n && A[left] < A[max]){ 
      max = left; 
     } 
     if (right <= n && A[right] > A[max]) { 
      max = right; 
     } 
     if (max != i) { 
      swap(A, i, max); 
      insert(A, max); 
     } 
    } 

    public static void HeapSort(int[] A) 
    { 
     n = A.length - 1; 

     for (int i = n/2; i >= 0; i--) 
      insert(A, i); 

     for (int i = n; i > 0; i--) { 
      swap(A, 0, i); 
      n--; 
      insert(A, 0); 
     } 
    } 

    public static void main(String[] args){ 
     int[] A = new int[] {9, 2, 8, 1, 4}; 
     System.out.println(java.util.Arrays.toString(arr)); 
     HeapSort(A); 
     System.out.println(java.util.Arrays.toString(arr)); 
    } 
} 

Es arbeitet mit einigen Arrays jedoch Arrays wie 9, 2, 8, 1, wird 4 erhalten sortiert nach 1, 4, 2, 8, 9. Warum sortiert das Array nicht korrekt?

Answer 1

if (left <= n && A[left] > A[i]){ 
    max = left; 
} 

Versuchen Sie dies und sehen. Ich habe das komplette Programm wie folgt gemacht. Dies funktioniert gut für die von Ihnen bereitgestellten Eingaben.

public class HeapSort { 

private static int n; 

private static void swap(int[] A, int a, int b) 
{ 
    int tmp = A[a]; 
    A[a] = A[b]; 
    A[b] = tmp; 
} 

private static void insert(int[] A, int i) 
{ 
    int left = i * 2; 
    int right = left + 1; 
    int max = i; 

    if (left <= n && A[left] > A[i]){ 
     max = left; 
    } 
    if (right <= n && A[right] > A[max]) { 
     max = right; 
    } 
    if (max != i) { 
     swap(A, i, max); 
     insert(A, max); 
    } 
} 

public static void HeapSort(int[] A) 
{ 
    n = A.length - 1; 

    for (int i = n/2; i >= 0; i--) 
     insert(A, i); 

    for (int i = n; i > 0; i--) { 
     swap(A, 0, i); 
     n--; 
     insert(A, 0); 
    } 
} 

public static void main(String[] args){ 
    int[] A = new int[] {19, 6, 28, 1, 0}; 
    int[] B = new int[] {1, 2, 4, 8, 9, 0}; 
    System.out.println(java.util.Arrays.toString(A)); 
    System.out.println(java.util.Arrays.toString(B)); 
    HeapSort(A); 
    HeapSort(B); 
    System.out.println(java.util.Arrays.toString(A)); 
    System.out.println(java.util.Arrays.toString(B)); 
} 

}

Hier ist die Ausgabe.

[19, 6, 28, 1, 0] 
[1, 2, 4, 8, 9, 0] 
[0, 1, 6, 19, 28] 
[0, 1, 2, 4, 8, 9] 

Answer 2

Wenn Sie left = i * 2 definieren, sollte die Wurzel Ihrer Haufen in A[1] gespeichert werden, nicht A[0]. Wenn Sie das Array nicht im Index 0 verwenden, können Sie immer sagen, dass die linken und rechten untergeordneten Elemente eines Knotens i2*i bzw. 2*i+1 sind.

Grundsätzlich in HeapSort sollten Sie 0 zu 1 ändern (es gibt 4 von ihnen). Testen Sie es mit Array {0, 9, 2, 8, 1, 4}.

Und auch ein Vergleich in insert ist auch falsch. Es sollte A[left] > A[max] sein.