Given an integer array arr, rearrange it in place into a max-heap (viewing the array as a complete binary tree: children of index i are 2i+1 and 2i+2; a max-heap has every node ≥ its children). Return the resulting array.
Use the bottom-up build: call max-heapify (sift-down) on every internal node, from index n/2 - 1 down to 0. This canonical procedure produces one specific max-heap arrangement.
Input: arr = [3, 9, 2, 1, 4, 5] Output: [9, 4, 5, 1, 3, 2] Bottom-up sift-down of indices 2, 1, 0 yields a valid max-heap.
Input: arr = [5, 4, 3, 2, 1] Output: [5, 4, 3, 2, 1] Already a max-heap, so nothing moves.
- 0 <= arr.length <= 10^5 - -10^9 <= arr[i] <= 10^9
There are two ways to turn an array into a heap. The tempting one is to insert elements one at a time, sifting each up — that's O(n log n). The better one, and the reason build-heap is a named trick, is bottom-up heapify: start from the last internal node (n/2 - 1) and call sift-down on each node down to the root. It runs in O(n).
Why bottom-up works: when you sift-down at node i, its two child subtrees are already valid max-heaps (you processed them earlier, since they have higher indices). So a single sift-down fixes node i's whole subtree. Processing indices in decreasing order maintains this invariant all the way to the root.
Why it's O(n), not O(n log n): sift-down costs are proportional to a node's height, not depth. Half the nodes are leaves (height 0, no work), a quarter are height 1, and so on. Summing height × count over all nodes converges to O(n) — the many cheap leaves dominate the count while the few expensive nodes near the root are rare.
“Min-heap or max-heap?”
Max-heap here — every parent ≥ its children.
“Why start at n/2 - 1?”
Leaves (indices n/2 .. n-1) are already trivial heaps; only internal nodes need sifting.
I sift-down every internal node from the last one up to the root.
Because children are heapified before their parent, one sift-down per node suffices — and it's O(n) overall, not O(n log n).
Worked example — arr = [3, 9, 2, 1, 4, 5]
last internal node = index 2 (value 2): child 5 -> swap -> [3, 9, 5, 1, 4, 2] index 1 (value 9): children 1,4 -> already largest -> no change index 0 (value 3): children 9,5 -> swap 9 -> [9, 3, 5, 1, 4, 2]; at index 1 children 1,4 -> swap 4 -> [9, 4, 5, 1, 3, 2] result = [9, 4, 5, 1, 3, 2]
Indices n/2 .. n-1 are already valid one-node heaps.
Each node's children are heapified before it, so one sift-down fixes its subtree.
Cost is proportional to node height; the sum over all nodes is linear.
| Insert one by one | Bottom-up heapify | |
|---|---|---|
| Idea | Add each element and sift it up | Sift-down every internal node, high index to low |
| Time | O(n log n) | O(n) |
| Space | O(1) extra (or O(n) new array) | O(1) |
Bottom-up heapify is the standard build; the two shipped versions differ only in recursive vs iterative sift-down. Full code is in the Approaches selector below.
Key takeaway
Build a heap by sifting down every internal node from n/2-1 to 0. Children are heapified before parents, so one pass suffices — O(n) time, O(1) space.
for i from n/2 - 1 down to 0:
sift_down(arr, i)