Building the Heap in Code

The trace sank the internal nodes from the last one back to the root. To write that as a loop, we need the index of the last internal node.

In the heap’s level-order array, the left child of index $i$ is at $2i+1$, and in a complete tree a node with no left child has no right child either. So index $i$ has children exactly when

$$2i+1<n,$$

and otherwise it is a leaf. Solving the inequality for $i$ splits the indices into two groups:

• Indices below $\lfloor n/2\rfloor$ are internal nodes.
• Indices at least $\lfloor n/2\rfloor$ are leaves.

So $\lceil n/2\rceil$ of the nodes are leaves and $\lfloor n/2\rfloor$ are internal. When $n$ is even, exactly half the nodes are leaves. When $n$ is odd, there is one more leaf than there are internal nodes. With Java’s integer division, the first leaf is index n / 2, and the last internal node is index n / 2 - 1. The leaves take up the back half of the array:

last internal = n/2-1
          ↓
  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 5 │ 3 │ 8 │░1░│░9░│░2░│
└───┴───┴───┴───┴───┴───┘
              ↑
      first leaf = n/2

A leaf has no children, so there is nothing to sink. The loop starts at the last internal node and counts down to the root:

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

For our six-element array, n / 2 - 1 is 2, so the loop runs 2, 1, 0, the three sinks we traced by hand.

The sink helper

sink is the operation from the binary heap chapter, adapted to a bare int[]. The array becomes a parameter, arr.length takes the place of size, and plain < and <= take the place of compare:

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

The index helpers are the same as in the binary heap chapter, now static. swap also takes the array as an argument:

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