271. Merge Two Binary Max-Heaps

You are given two binary max-heaps, each as an array in the usual level-order representation (node i's children sit at 2i+1 and 2i+2), of sizes n and m respectively. Merge them into one array of size n+m by concatenating the first heap's array followed by the second heap's array, then convert that combined array 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 repeatedly swapping it with its larger child (preferring the left child when both children are equal) until the heap property holds there. Print the resulting array.

Input: The first line contains an integer n followed by a line of n space-separated integers for the first max-heap. The next line contains an integer m followed by a line of m space-separated integers for the second max-heap. Output: Print the resulting array after merging both heaps' arrays and converting the combination into a valid max-heap.

1 <= n, m <= 10^5

This relies on the exact SAME build-heap procedure used for both 'sort using heap sort' and 'convert min-heap to max-heap' - recognizing build-heap as a single reusable tool across multiple heap problems is a valuable, efficient pattern to internalize.

Given two separate valid max-heaps, combine them into a single, valid max-heap containing all their elements. Brute force: Extract all values from both heaps, combine and sort them, then rebuild a fresh heap from scratch, or insert each of the second heap's elements one at a time into the first heap - both work but do more comparisons than necessary given that most of the combined array is ALREADY internally heap-ordered within each original half. Optimised: Since each ORIGINAL heap already individually satisfies the max-heap property, simply concatenating them and running build-heap ONE time on the whole combined array re-establishes the property everywhere in O(n+m) - there's no need to treat this as inserting elements one at a time, since build-heap efficiently handles the whole array at once regardless of its starting arrangement.

Concatenate the two arrays, then build a heap incrementally by inserting elements one at a time: append each element to the end of a growing array and 'sift it up', repeatedly swapping it with its parent while it is larger, until the heap property holds from that leaf up to the root. Each of the n+m insertions costs at most O(log(n+m)) for its sift-up, so this is the same asymptotic cost as sorting, but it builds the heap incrementally the way real heap-insert operations do, rather than relying on a general-purpose sort. Time: O((n+m) log(n+m)) Space: O(1) extra

Concatenate the two arrays exactly as given with no sorting or one-by-one insertion, then starting from the last non-leaf node down to the root, sift each node down by repeatedly swapping it with its larger child (preferring the left child on a tie) until the heap property holds locally at that position. This matches the array's specified construction exactly. Although it looks like it should cost O((n+m) log(n+m)) since there are O(n+m) nodes each doing up to O(log(n+m)) work, a tighter accounting shows most nodes are near the bottom of the tree and need very little sifting, so the whole procedure actually completes in linear time, making it asymptotically better than either building via sort or via repeated insertion. Time: O(n+m) Space: O(1)

Concatenate the two heap arrays into one combined array, then simply sort that combined array in descending (non-increasing) order. This always produces a valid max-heap array because in a descending sequence every element is greater than or equal to every element that comes after it, and since a node's children always sit at strictly larger array indices than the node itself, the parent-greater-than-children property is automatically satisfied everywhere. It is correct and simple, but it does more comparison work than necessary and does not reproduce the specific left-preferring bottom-up build order the problem describes. Time: O((n+m) log(n+m)) Space: O(log(n+m))

1. Concatenate the first heap's array followed by the second heap's array into one combined array. 2. This combined array is only 'broken' as a heap around where the second array's root landed - so run the standard bottom-up build-heap procedure on the WHOLE combined array (starting from its own last non-leaf index). 3. The result is a single valid max-heap containing every element from both original heaps.

Time: O(n+m) - the standard build-heap procedure applied once to the combined array of size n+m. Space: O(1) extra space beyond the concatenated array itself.

n = 1 or m = 1 (a single-node heap being merged in), and n, m each up to 10^5 to confirm heapify performance on the combined array.

Be ready to explain why simple concatenation-plus-build-heap beats repeatedly inserting one heap's elements into the other one at a time (which would cost O(m log(n+m)) for m insertions) - a nice efficiency comparison to have ready.