Given an integer array arr (viewed as a complete binary tree in array form: the children of index i are 2i+1 and 2i+2) and an index i, perform max-heapify at i — sink the element at i down to its correct place so the subtree rooted at i satisfies the max-heap property (each node ≥ its children). Return the resulting array.
To sink it: compare arr[i] with its two children; if the larger child exceeds it, swap them and continue from the child's position. If i is out of range, return the array unchanged.
Input: arr = [1, 10, 5, 8, 3], i = 0 Output: [10, 8, 5, 1, 3] 1 sinks past 10 then past 8 to reach a leaf.
Input: arr = [9, 7, 8, 1, 2], i = 0 Output: [9, 7, 8, 1, 2] 9 is already ≥ both children, so nothing moves.
- 1 <= arr.length <= 10^5 - -10^9 <= arr[i] <= 10^9 - 0 <= i
Max-heapify (also called sift-down or percolate-down) is the single repair operation every heap is built from. The element at i may be smaller than a child, violating the max-heap property locally. To fix it, find the larger of its two children; if that child is bigger than arr[i], swap them — now the violation (if any) has moved one level down, to the child's old position. Repeat from there until the element is ≥ both its children or it becomes a leaf.
Each step drops one level, so heapify is O(log n) time and touches a single root-to-leaf path. The recursive and iterative versions do exactly the same swaps; the iterative one just follows the index down instead of recursing, using O(1) space.
“Do I swap with either child or a specific one?”
The larger child — otherwise the swapped-up value might still violate the property.
“When do I stop?”
When the element is ≥ both children, or it has no children (a leaf).
I compare the element at i to its larger child; if the child is bigger I swap and move down to that child.
I repeat until it sits above both children or reaches a leaf — one root-to-leaf path, O(log n).
Worked example — arr = [1, 10, 5, 8, 3], i = 0
i=0: children 10,5 -> larger is 10 (>1) -> swap -> [10, 1, 5, 8, 3], continue at 1 i=1: children 8,3 -> larger is 8 (>1) -> swap -> [10, 8, 5, 1, 3], continue at 3 i=3: no children -> stop result = [10, 8, 5, 1, 3]
Swapping with the smaller child could leave the larger child still greater than its parent.
Each swap pushes the out-of-place value one level deeper, never back up.
Heapify follows a single root-to-leaf path, so it costs O(height).
| Recursive sift-down | Iterative sift-down | |
|---|---|---|
| Idea | Swap with larger child, recurse into it | Same, but loop down following the index |
| Time | O(log n) | O(log n) |
| Space | O(log n) stack | O(1) |
Both produce the identical array; the iterative version avoids the recursion stack. Full code is in the Approaches selector below.
Key takeaway
Max-heapify sinks arr[i]: swap it with its larger child whenever that child is bigger, following the swap down one level at a time until it fits or becomes a leaf. O(log n) time, one root-to-leaf path.
while i has a child bigger than arr[i]:
largest = index of the bigger child
swap(arr[i], arr[largest]); i = largest