Building a Heap Bottom-Up

The questions in this section are about rearranging an array of $n$ values into a binary min-heap in place. The array is read as a tree in level order. Index 0 is the root, and the children of index $i$ are at $2 i + 1$ and $2 i + 2$ .

A binary min-heap has two properties:

The structure property: the tree is complete. Every level is full except possibly the last, and the last level fills from the left.
The order property: every node is no larger than its children.

sink(arr, i) moves the value at index i down. At each step it swaps the value with its smaller child, and it stops when the value is no larger than either child or has no children.

Solution

It already satisfies the structure property. An array has no gaps, so reading it in level order fills every level from the left, and the tree is complete. Only the order property has to be fixed.

Solution

One sink at a node is guaranteed to make the subtree rooted at that node a heap when both of the node’s subtrees are already heaps.

Bottom-up meets that condition. Leaves are one-node heaps, and by the time the build reaches a node, both of its subtrees have already been made into heaps. So each internal node is sunk once and never revisited.
Top-down does not meet it. When the root is sunk, its subtrees are still out of order. A later sink lower in the tree can move a small value up and break the order property above it, so nodes have to be checked again.

Solution

It starts at index n / 2 - 1, the last internal node.

Index $i$ has a child exactly when its left child exists, that is, when $2 i + 1 < n$ . The largest $i$ that satisfies this is n / 2 - 1. Every index from n / 2 onward is a leaf, which is already a one-node heap, so it needs no sink.