Build Heap

Given an unordered array, build-heap treats it as the level-order layout of a complete binary tree and repairs it bottom-up. All leaves are already valid heaps of size one, so the first useful repair starts at the last internal node: index n/2 - 1.

From there, apply sift-down at each index moving backward to 0. By the time a node is repaired, both of its child subtrees have already been repaired. That is exactly the precondition heapify needs.

In a zero-based heap array, any index greater than or equal to n/2 has no left child because 2i+1 >= n. Those positions are leaves. Calling heapify on leaves would do nothing, so build-heap begins at n/2 - 1, the parent of the last element or near it.

For [9,4,7,1,3,6], indices 3, 4, and 5 are leaves. The loop starts at index 2, then 1, then 0, gradually turning the whole array into a valid min heap such as [1,3,6,4,9,7] depending on equal-choice details.

A loose argument says there are n nodes and each heapify is O(log n), but that overcounts. Most nodes are near the bottom and can move only a few levels. About half the nodes are leaves with height 0, about a quarter have height 1, about an eighth have height 2, and so on.

The total work is proportional to n/2 * 0 + n/4 * 1 + n/8 * 2 + n/16 * 3 + ..., which sums to O(n). The small number of tall nodes cannot dominate the many short repairs. This is the key build-heap proof interviewers expect.

Repeatedly inserting n elements into an empty heap costs O(n log n) because every insertion may climb a logarithmic path. Bottom-up build-heap is better when all elements are already available because it exploits the existing complete-tree layout and the fact that leaves need no work.

Use repeated offer() when data arrives online. Use build-heap when the array is known upfront, such as heap sort initialization, converting a batch into a priority queue, or implementing a custom heap from raw input.