Given an integer array arr that currently represents a min-heap (every node ≤ its children), rearrange it in place into a max-heap (every node ≥ its children) and return it. The array is viewed as a complete binary tree: children of index i are 2i+1 and 2i+2.
Input: arr = [1, 3, 6, 5, 9, 8] Output: [9, 5, 8, 1, 3, 6] Rebuilt bottom-up into a valid max-heap.
Input: arr = [1, 2, 3, 4, 5, 6] Output: [6, 5, 3, 4, 2, 1] Build-max-heap; note this is not simply the reversed array.
- 0 <= arr.length <= 10^5 - -10^9 <= arr[i] <= 10^9 - arr is a valid min-heap
The tempting shortcut — "a min-heap reversed is a max-heap" — is wrong. Reversing [1, 2, 3, 4, 5, 6] gives [6, 5, 4, 3, 2, 1], which happens to be a max-heap here, but in general reversal does not produce a valid max-heap (try [1, 5, 6, 8, 9, 7]). The min-heap structure gives you essentially no head start: the smallest element is at the root, which is exactly where the largest now needs to be, and the internal order is useless for a max-heap.
So you simply build a max-heap from scratch with the standard bottom-up heapify: call max-heapify (sift-down) on every internal node from n/2 - 1 down to 0. Because leaves are already valid heaps and each node's children are processed first, one pass suffices — and it's O(n), same as reading the array. The fact that the input was a min-heap doesn't speed this up or slow it down.
“Can I just reverse the array?”
No — reversal doesn't yield a valid max-heap in general.
“Does the min-heap input help?”
Not asymptotically — you rebuild in O(n) either way.
I can't reuse the min-heap order, so I rebuild: max-heapify every internal node bottom-up.
That's the O(n) build-heap, and it produces a valid max-heap regardless of the starting arrangement.
Worked example — arr = [1, 3, 6, 5, 9, 8] (a min-heap)
index 2 (6): child 8 -> swap -> [1, 3, 8, 5, 9, 6] index 1 (3): children 5,9 -> swap 9 -> [1, 9, 8, 5, 3, 6] index 0 (1): children 9,8 -> swap 9 -> [9, 1, 8, 5, 3, 6]; at index 1 children 5,3 -> swap 5 -> [9, 5, 8, 1, 3, 6] result = [9, 5, 8, 1, 3, 6]
The min-heap order gives no valid max-heap for free.
Bottom-up heapify rebuilds correctly from any arrangement.
Build-heap is linear; the starting order doesn't change that.
| Recursive build | Iterative build | |
|---|---|---|
| Idea | Bottom-up max-heapify, recursive sift-down | Bottom-up max-heapify, iterative sift-down |
| Time | O(n) | O(n) |
| Space | O(log n) | O(1) |
Both rebuild the array as a max-heap; they differ only in recursive vs iterative sift-down. Full code is in the Approaches selector below.
Key takeaway
You can't reuse min-heap order — rebuild. Max-heapify every internal node from n/2-1 down to 0. O(n) time, O(1) space (iterative sift-down).
for i from n/2 - 1 down to 0:
max_heapify(arr, i)