Two Changes to sink

To sort in increasing order we need a max-heap, so that the largest element is the one swapped to the back. That takes two changes to sink.

First change: a max-heap

In a max-heap every node is no smaller than its children. So sink slides a node down past its larger child while the node is smaller than that child.

The two comparisons reverse, and smaller is renamed larger:

private static void sink(int[] arr, int i) {
  int n = arr.length;
  while (leftChild(i) < n) {
    int larger = leftChild(i);
    int right = rightChild(i);
    if (right < n && arr[right] > arr[larger]) {
      larger = right;                    // pick the LARGER of the two children
    }
    if (arr[i] >= arr[larger]) {
      break;                             // node i already sits no smaller than its children
    }
    swap(arr, i, larger);
    i = larger;
  }
}

Second change: a heap-size parameter

Right now sink measures the heap against arr.length, the whole array. That was fine while building, when the heap really is the whole array. But during the sort the heap shrinks: after each removal, one more finished element sits in the tail, and that element must never move again.

Suppose the first removal has just swapped the largest value to the back:

┌───┬───┬───┬───┬───┬───┐
│ 2 │ 5 │ 8 │ 1 │ 3 │░9░│
└───┴───┴───┴───┴───┴───┘
  ↑
new root

Now we sink the new root 2. If sink still ranged over the whole array, it would slide 2 down to index 2, see 9 at index 5 as its child, and swap 9 back up into the heap, which undoes the removal we just made.

So sink has to know where the heap ends. We pass that in as size, and sink only looks at children with index below it:

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;
  }
}