1
$\begingroup$

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this?

The easiest way is to consider 2 max heaps an array with $2n$ elements and build a min heap with $O(n)$ complexity. Is there an algorithm with a complexity better than $O(n)$ ?

$\endgroup$
1
$\begingroup$

I guess you're thinking that there may be a faster way because if you want to merge two min heaps into a third min heap, is can be done in $O(\log n)$ by creating a $-\infty$ node in $O(1)$, making the roots of both heaps be children of that new node in $O(1)$, and extracting the min of the heap in $O(\log n)$.

But in your case, it can't be done. Clearly, building a min heap is harder than finding the minimum. But the minimum could be any of the leaves of the max heaps, so you have $O(n)$ elements of which you want to find the minimum. Clearly, you have to at least read all those elements and so you take at least $O(n)$ time. So it's $\Theta(n)$.

(Note that when merging two min heaps into a min heap, the minimum has to be one of the two roots, so it can be found in $O(1)$. But in the second case, there are too many nodes that could potentially be (i.e. are for some values of the heap) the minimum)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy