Как исправить программу для пирамидальной сортировки?

Question

[Аркадий Саакян]

Почему она неправильно сортирует массив? Что не так?

public class Main {
  
  public static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2; i >= 0; i--) {
      heapify(a, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
      swap(a, i, 0);
      heapify(a, i, 0);
    }
  }
  
  public static void heapify(int[] heap, int n, int i) {
    int l = left(i);
    int r = right(i);
    int largest = i;
    if (l < n && heap[l] > heap[i]) {
      largest = l;
    }
    if (r < n && heap[r] > heap[i]) {
      largest = r;
    }
    if (i != largest) {
      swap(heap, i, largest);
      heapify(heap, n, largest);
    }
  }
  
  public static int right(int i) {
    return 2 * i + 2;
  }
  
  public static int left(int i) {
    return 2 * i + 1;
  }
  
  public static void swap(int[] heap, int i1, int i2) {
    int temp = heap[i1];
    heap[i1] = heap[i2];
    heap[i2] = temp;
  }
  
  public static void main(String[] args) {
    int[] A = new int[] {2, 3, 1, 5, 4};
    heapSort(A);
    for (int i = 0; i < A.length; i++)
      System.out.println(A[i]);
  }
}

Answer 1

[mayton2019]

Возьми маленький рандомный массив на 10 элементов. И распечатай его стостояние на каждом цикле сортировки.
Там будет сразу видно где ты боков напорол.

И процедуру хипифай проверь отдельным тестом. Для всех i должен работать инвариант:

heap[i] >= heap[i*2 + 1]
heap[i] >= heap[i*2 + 2]