Каков правильный способ реализации heapsort?

Question

Я провожу последние 5 часов, глядя на так много видео и чтений (включая cormen), и я наконец решил написать свой собственный heapsort, чтобы проверить его. Я в основном беру некоторые входы от стандартного ввода и сохраняя их в массиве, а затем я буду использовать heapsort для их сортировки.

Ниже мой код

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

    public static void maxHeapify(int[] A, int i) 
    { 
     int left = 2*i; 
     int right = 2*i + 1; 
     int largest = 0; 
     if(left <= n && A[left] > A[i]) 
      { 
       largest=left; 
      } 
      else 
      { 
       largest=i; 
      } 

      if(right <= n && A[right] > A[largest]){ 
       largest=right; 
      } 
      if(largest!=i){ 
       int temp = A[i]; 
       A[i] = A[largest]; 
       A[largest] = temp; 
       maxHeapify(A, largest); 
      } 
     } 

Мой массив ввода является: 3,5,8,7,1,13,11,15,6 Выход: 3,15,13,11 , 6,8,5,7,1

выход, очевидно, не так, как первый индекс должен содержать наибольшее значение 15.

Итак я решил взять старый добрый путь с ручкой и записную книжку и отслеживание код и понял, что в buildHeap i должен быть n-1/2. Однако он также не дал мне правильный результат. Я действительно потерялся и разочарован. Может ли кто-нибудь пролить свет на то, что я делаю неправильно?

Answer 1

Ваших расчетов индекса выключено:

int left = 2*i; 
int right = 2*i + 1; 

Если i является 0, то мы хотим left и right быть 1 и 2. Если i равно 1, то left и right должен быть 3 и 4, и скоро. Расчеты должны быть:

int left = 2*i + 1; 
int right = 2*i + 2; 

Кроме того,

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

Условием является i > 0. Тело цикла будет выполняться только тогда, когда i > 0, поэтому элемент с индексом 0 (т. Е. Первый) не будет перемещаться. Условие должно быть i >= 0.