Problem

Given an integer array arr of size n, rearrange it in place so that it satisfies the max-heap property: for every index i, arr[i] >= arr[2i+1] and arr[i] >= arr[2i+2] where those indices exist. Do it in O(n) time, not O(n log n).

Input / Output

• Input: integer array arr.
• Output: the array arranged as a max-heap (any valid arrangement is accepted).

Examples

Example 1 Input: arr = [1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17] Output: [17, 15, 13, 9, 6, 5, 10, 4, 8, 3, 1] Explanation: The root 17 is the maximum; every parent is >= its children.

Example 2 Input: arr = [2, 1] Output: [2, 1]

Constraints

• 1 <= n <= 10^6

Approach

Why not insert one at a time? Inserting n elements with sift-up costs O(n log n) in the worst case.

Bottom-up construction (Floyd's method). Indices n/2 .. n-1 are leaves and trivially satisfy the heap property. Process the internal nodes from the last one (n/2 - 1) down to 0, calling siftDown(i) on each:

siftDown(i):
    while true:
        l = 2i + 1; r = 2i + 2; largest = i
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        swap(arr[i], arr[largest]); i = largest

When we reach node i, both of its subtrees are already heaps, so a single sift-down restores the property for the subtree rooted at i.

Why it is O(n). A node at height h sifts down at most h levels, and there are about n / 2^(h+1) nodes at height h. Total work ≈ Σ h · n / 2^(h+1), and Σ h / 2^h converges to 2, so the sum is O(n). Being able to state this bound is the main thing interviewers look for.

Complexity

• Time: O(n)
• Space: O(1)

Related

Heap sort (build heap, then repeatedly extract the max), building a priority queue from a bulk collection, and the "k-th largest element" problem where an O(n) build followed by k extractions beats sorting.