Problem

Given an integer array arr of size n, transform it in place into a valid max-heap: for every index i, arr[i] >= arr[2i+1] and arr[i] >= arr[2i+2] whenever those children exist. Also implement the heapify(arr, n, i) routine that repairs the heap property at a single index assuming both of its subtrees are already heaps.

Input / Output

• Input: an unsorted integer array.
• Output: the same array rearranged into a max-heap (any valid heap arrangement is accepted).

Examples

Example 1 Input: arr = [4, 10, 3, 5, 1] Output: [10, 5, 3, 4, 1] Explanation: 10 is the root; its children 5 and 3 are smaller; 5's children 4 and 1 are smaller.

Example 2 Input: arr = [1, 2, 3, 4, 5, 6] Output: [6, 5, 3, 4, 2, 1]

Constraints

• 1 <= n <= 10^6
• -10^9 <= arr[i] <= 10^9

Approach

The heapify (sift-down) step. At index i, compare arr[i] with its left child 2i+1 and right child 2i+2. Let largest be the index of the biggest of the three. If largest != i, swap arr[i] and arr[largest] and recursively heapify at largest — the swapped-down value may still violate the property further down. Each call moves down one level, so a single heapify is O(log n).

Building the heap. Leaves (indices n/2 to n-1) are trivially heaps. Starting from the last non-leaf index n/2 - 1 and moving to index 0, call heapify on each. Because each node's subtrees are already valid by the time we reach it, the entire array becomes a heap.

Why building is O(n), not O(n log n). Most nodes are near the bottom and sift down only a few levels. Summing (number of nodes at height h) × h over all heights gives n × Σ h/2^h, which converges to a constant times n. This is a classic interview follow-up.

Complexity

• heapify: O(log n) time, O(log n) stack (or O(1) iteratively).
• : O(n) time, O(1) extra space.