Ошибка программы Java heapsort во время выполнения

Question

Мой код работает во время компиляции, но ошибка выполнения указывает на условие if в моей функции MaxHeapify. Я отметил это. Любая помощь была бы просто прекрасна, и заставила бы меня перестать ударить головой о стену.

public class HeapSort { 

    public static void main(String[] args) { 
     int A[] = {-100, 1, 2, 5, 7, 2, 9}; 
     Heapsort(A); 
     //System.out.println(A.length); 
     for (int x = 1; x < A.length; x++) { 
      System.out.println(A[x] + " "); 
     } 
    } 

    public static void Build_MAX_heap(int A[]) { 
     int n = A.length; 
     for (int i = n/2; i >= 1; i--) { 
      MAX_heapify(A, i); 
     } 
    } 

    public static void MAX_heapify(int A[], int i) { 
     int heapsize = A.length; 
     int l = 2 * i; 
     int r = 2 * i + 1; 
     //find the largest of A[i].A[l],A[r] 
     int largest = i; 
     if (A[l] > A[largest]) { 
      largest = l; 
      if (A[l] > A[largest] && l <= heapsize) { 
       largest = l; 
      } 
      if (A[r] > A[largest] && r <= heapsize) {  //runtime error here 
       largest = r; 
      } 
      if (largest != i) { 
       int temp = A[i]; 
       A[i] = A[largest]; 
       A[largest] = temp; 
       MAX_heapify(A, largest); 
      } 
     } 
    } 

    public static void Heapsort(int A[]) { 

     Build_MAX_heap(A); 
     int heapsize = A.length; 
     for (int last = heapsize; last >= 2; last--) { 
      int temp = A[1]; 
      A[1] = A[last]; 
      A[last] = temp; 
      heapsize--; 
      MAX_heapify(A,1); 
     } 
    } 
} 

Answer 1

Переменная r установлен на:

int r = 2 * i + 1; 

В первом случае цикла:

for (int i = n/2; i >= 1; i--) { 
    MAX_heapify(A, i); 
} 

i является n/2

так, чтобы функции передается:

MAX_heapify(A,n/2); 

и r является 2 * (n/2) + 1 которого n+1

, когда вы хотите сделать эту линию

if (A[r] > A[largest] && r <= heapsize) { 

затем A[r] является A[n+1]=A[A.length+1] - это вызывает IndexOutOfBoundsException

Answer 2

Вы делаете вас ограничивает проверки r (и l тоже в предыдущем заявлении) после проверки элемента по индексу r. Если r не соответствует границам, первая половина выражения вызовет исключение и никогда не будет проверена границами.

Ваш если заявления должны быть структурированы

if (r < heapsize && A[r] > A[largest]) ... 

так, что вы знаете, что в пределах, прежде чем начать пытаться получить доступ к массиву. Кроме того, поскольку массивы нуль-индексируются, индекс heapsize недействителен, поэтому r должен быть меньше, не меньше или равно.

Answer 3

Вашей проблемы заключается в том, что ваш проверяет А [г] перед проверкой, если r находится за пределами допустимого диапазона , поэтому я попытаюсь изменить код таким образом

public class HeapSort { 

public static void main(String[] args) { 
    int A[] = {-100, 1, 2, 5, 7, 2, 9}; 
    Heapsort(A); 
    //System.out.println(A.length); 
    for (int x = 1; x < A.length; x++) { 
     System.out.println(A[x] + " "); 
    } 
} 

public static void Build_MAX_heap(int A[]) { 
    int n = A.length; 
    for (int i = n/2; i >= 1; i--) { 
     MAX_heapify(A, i); 
    } 
} 

public static void MAX_heapify(int A[], int i) { 
    int heapsize = A.length; 
    int l = 2 * i; 
    int r = 2 * i + 1; 
    //find the largest of A[i].A[l],A[r] 
    int largest = i; 
    if (A[l] > A[largest]) { 
     largest = l; 
     if (A[l] > A[largest] && l <= heapsize) { 
      largest = l; 
     } 
     if (r<=heapsize && A[r] > A[largest]) {  //modification here 
      largest = r; 
     } 
     if (largest != i) { 
      int temp = A[i]; 
      A[i] = A[largest]; 
      A[largest] = temp; 
      MAX_heapify(A, largest); 
     } 
    } 
} 

public static void Heapsort(int A[]) { 

    Build_MAX_heap(A); 
    int heapsize = A.length; 
    for (int last = heapsize; last >= 2; last--) { 
     int temp = A[1]; 
     A[1] = A[last]; 
     A[last] = temp; 
     heapsize--; 
     MAX_heapify(A,1); 
    } 
} 

}