281. Convert a Min-Heap to a Max-Heap

Given an array representing a valid min-heap (0-indexed, node i's children sit at 2i+1 and 2i+2), convert it into a valid max-heap using the standard bottom-up build-heap procedure: for each index from the last non-leaf node up to the root, sift it down by swapping it with its larger child (preferring the left child when both children are equal) until the max-heap property holds there. Print the resulting array.

Input: The first line contains an integer n. The second line contains n space-separated integers representing the min-heap in its level-order array form. Output: Print the resulting array after converting it to a valid max-heap.

1 <= n <= 10^5

The array's EXISTING min-heap property is actually irrelevant to the solution - build-heap works identically on ANY array, ordered or not, which is why this problem doesn't need any special 'conversion' logic beyond just running standard build-heap for the opposite heap type.

Given an array that's already a valid min-heap, rearrange it into a valid max-heap. Brute force: Extract all the values, sort them, and rebuild an entirely fresh max-heap from the sorted list, or repeatedly insert each value into a brand-new empty max-heap - both work but do more work than simply re-heapifying the existing array in place. Optimised: The standard bottom-up build-heap procedure works on ANY array of values, regardless of their CURRENT arrangement - since it doesn't rely on the array already being sorted or partially heap-ordered in a useful way, you can apply it directly to the min-heap's array (treating it as raw, unordered data) to build a max-heap in O(n), without needing to first 'undo' the min-heap structure.

Repeatedly remove the minimum element from the given min-heap using standard extract-min (swap the root with the last element, shrink the heap, sift the new root down) to read off all n values in ascending order, then insert each of those values one at a time into a brand-new, initially empty array using standard max-heap insertion (append, then bubble up). This does produce a valid max-heap containing the same values, but it pays for a full heap drain plus n independent O(log n) insertions. Time: O(n log n) Space: O(n)

Treat the array as an arbitrary unordered array in place, and repeatedly sweep over every internal node checking whether it is at least as large as both children; whenever a violation is found, swap the node down past its larger child. Repeat full sweeps over the whole array until an entire pass produces no swaps. This eventually converges to a valid max-heap without any extra memory, but because a single pass only fixes local violations and disturbed nodes may need re-checking in later passes, it can take many passes to fully settle. Time: O(n^2) Space: O(1)

Perform the standard single-pass bottom-up build-heap: starting from the last non-leaf node and walking backward to the root, sift each node down exactly once, comparing it against its larger child (preferring the left child on ties) and swapping and continuing until the local max-heap property holds. Because most nodes live near the bottom of the tree and need very little sifting while only a few nodes near the root travel far, the amortized total work across all sift-downs is linear rather than n log n, and processing bottom-up with this exact tie-breaking rule is also what produces the specific deterministic array the problem expects. Time: O(n) Space: O(1)

1. Ignore the fact that it currently satisfies the min-heap property entirely - just treat the array as plain, unordered data. 2. Run the standard bottom-up build-heap procedure FOR A MAX-HEAP: starting from the last non-leaf index (n/2 - 1) down to the root, sift each node down by swapping with its LARGER child until the max-heap property holds there. 3. This produces a valid max-heap containing the same values.

Time: O(n) - the standard build-heap procedure, run bottom-up, achieves this despite looking like it might cost O(n log n) (a well-known tighter bound for build-heap). Space: O(1) extra space - the conversion happens directly within the original array.

n = 1 (heap unchanged), and n = 10^5 to confirm the bottom-up heapify runs efficiently.

Be ready to explain WHY build-heap is O(n) rather than O(n log n) - most nodes are near the bottom of the tree and need very few sift-down swaps, and this weighted average works out to a linear total, a classic and often-tested amortized-analysis result.