Implementing Heapsort

In this section, you will fill in the outline below. It is an in-place heapsort on an int[]. The array is read as a tree in level order. heapSort and the index and swap helpers are already written.

public final class HeapSort {

  // Sorts arr in ascending order. Assumes arr is not null.
  public static void heapSort(int[] arr) {
    buildHeap(arr);  // rearrange the array into a heap
    sortdown(arr);   // empty the heap into ascending order
  }

  // Rearranges arr into a heap.
  private static void buildHeap(int[] arr) { ... }

  // Repeatedly swaps the root to the last slot of the heap, shrinks the heap
  // by one, and restores the heap, until one element is left.
  private static void sortdown(int[] arr) { ... }

  // The heap occupies arr[0] to arr[size - 1]. Moves arr[i] down until the
  // heap's order property holds at its position.
  private static void sink(int[] arr, int i, int size) { ... }

  // The left child of the node at index i.
  private static int leftChild(int i) {
    return 2 * i + 1;
  }

  // The right child of the node at index i.
  private static int rightChild(int i) {
    return 2 * i + 2;
  }

  // Exchanges arr[i] and arr[j].
  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

private static void sink(int[] arr, int i, int size) {
  while (leftChild(i) < size) {
    int larger = leftChild(i);
    int right = rightChild(i);
    if (right < size && arr[right] > arr[larger]) {
      larger = right;
    }
    if (arr[i] >= arr[larger]) {
      break;
    }
    swap(arr, i, larger);
    i = larger;
  }
}

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

private static void sortdown(int[] arr) {
  for (int end = arr.length - 1; end > 0; end--) {
    swap(arr, 0, end);
    sink(arr, 0, end);
  }
}