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

Question

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)$?

Answer 1

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.