public class HeapSort {

  private static int getLeft(int index) {
      return index * 2 + 1;
  }
  private static int getRight(int index) {
      return index * 2 + 2;
  }
  private static void exchange (int[] arr, int first, int second) {

      int temp = arr[first];
      arr[first] = arr[second];
      arr[second] = temp;
  }
  private static void maxHeapify (int[] arr, int size, int index) {

      int left = getLeft(index);
      int right = getRight(index);
      int maxIndex = index;

      if (left < size && arr[left] > arr[maxIndex])
        maxIndex = left;

      if (right < size && arr[right] > arr[maxIndex])
        maxIndex = right;

      if (index != maxIndex) {

          exchange(arr, index, maxIndex);

          maxHeapify (arr, size, maxIndex);
      }

  }
  private static void buildMaxHeap (int[] arr) {
      int size = arr.length;
      for (int i = ((size-1) / 2); i >= 0; i --) {
          // Do max-heapify on the i.
          maxHeapify (arr, size, i);
      }
  }
  public static void heapSort(int[] arr) {
      int size = arr.length;

      buildMaxHeap(arr);

      for (int i = size - 1; i >= 0; i--) {

          exchange (arr, 0, i);

          maxHeapify (arr, i, 0);

          showArray(arr);

      }
  }

  public static void showArray (int[] arr) {
      int size = arr.length;
      for (int i = 0; i < size; i++)
          System.out.print(String.format("%-4d", arr[i]));
      System.out.println();
  }


  public static void main (String[] args) {

      int[] arr = {53, 42, 86, 11, 27, -5, 89, 0};

      heapSort(arr);

      showArray(arr);
  }
}

/*output:

86  42  53  11  27  -5  0   89
53  42  0   11  27  -5  86  89
42  27  0   11  -5  53  86  89
27  11  0   -5  42  53  86  89
11  -5  0   27  42  53  86  89
0   -5  11  27  42  53  86  89
-5  0   11  27  42  53  86  89
-5  0   11  27  42  53  86  89
-5  0   11  27  42  53  86  89


*/