Skipping the Leaves of a Complete Binary Tree

Floyd's heapify algorithm works from the bottom of the tree upwards: compare each node to its children and move nodes down (sink) so that parent nodes are always larger than their children.

Observation: In a ranked array representation of a complete binary tree with $n$ elements, index $p = n/2$ is the index of the rightmost interior node.

Proof: In a complete binary tree with $n$ elements, the index of the last leaf is $n$ (recall we use 1-based indexing.) Let $p = n/2$ be the index of the parent of said leaf.

The element at index $p$ must be an interior node since it is the parent of a leaf. It remains to be shown that $p$ is the rightmost such node.

Suppose element $p$ has an interior node $q$ to its right on the same level. Since $q$ is an interior node, it must have a child. Since $q$ is to the right of $p$, the child of $q$ would be to the right of the child of $p$, which has index $n$. But this would contradict the hypothesis that $n$ is the last index of the complete binary tree.

Therefore, $p = n/2$ is the index of the last interior node.

The implication of this observation is to simplify the implementation of the heapify process:

private static void heapify(Integer[] data) {
  for (int i = numNodes / 2; i >= 1; i--) {
    sink(data, i);
  }
}