# Proving that converting min-heaps to max-heaps requires time Ω(n)

Suppose I have a min-heap SH stored inside an array. I can perform the operations:

• view-min(SH) in $O(1)$
• extract-min(SH) in $O(\log n)$
• insert(SH) in $O(\log n)$
• is-empty(SH) in $O(1)$

If I want to build a max-heap BH from the first one, the naive algorithm I can implement is obviously

BH <- build-heap()
while not is-empty(SH) do             O(n)
elem <- extract-min(SH)           -> O(logn)
insert(BH, elem)                  -> O(logn)
done


whose complexity is obvously $O(n \log n)$ worst case. Is this the best algorithm or there is any algorithm whose complexity is lower? Yes

According to Wikipedia we can at least achieve $O(n)$. Without making any assumption about our array being an heap. Can we use this fact to achieve $O(\log n)$ complexity? No

It should be impossible, because we have to deal with any of the $n$ items at least one time. Does this prove that the conversion is $\Theta(n)$?

You could argue that the level-hierarchy gives more information, but not by much. Assuming a full max-heap of distinct values the $min$ element is on the deepest level of $\frac{n+1}{2}$ nodes. Unless there is some additional ordering to the heap, it would then take $\Omega(n)$ just to find the $min$ element.
• You don't need the assumption of a full heap. The minimum is always on the frontier, which is of size $(n+1)/4 < \_ \leq (n+1)/2$. – Raphael Aug 23 '17 at 14:34
• That said, to make this rigorous we can add a adversary argument: If the algorithm looks at only $o(n)$ elements, so in particular not all of the frontier (for some large enough tree). So we hide the new minimum there, at a position the algorithm doesn't check. (Only works for deterministic algorithms, of course.) – Raphael Aug 23 '17 at 14:39