public class HeapSort {
  public static void main(String[] args) {
    int[] array = new int[] {3, 2, 1, 5, 6, 4};
    new HeapSort().heapSort(array);
  }
  
  private void heapSort(int[] array) {
    int heapSize = array.length;
    for (int i = heapSize / 2 - 1; i >= 0; i--) {
      maxHeapify(array, i, heapSize);
    }
  }
  
  private void maxHeapify(int[] array, int i, int heapSize) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = left;
    
    // 判断左子节点是否比当前节点大
    if (left < heapSize && array[left] > array[largest]) {
      largest = left;
    }
    
    // 判断右子节点是否比当前节点大
    if (right < heapSize && array[right] > array[largest]) {
      largest = right;
    }
    
    // 如果最大值的下标不是i，说明有 左子节点/右子节点 比当前节点大
    if (largest != i) {
      swap(array, i, largest);
      maxHeapify(array, largest, heapSize);
    }
  }
  
  private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}