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 &lt;- build-heap() 
while not is-empty(SH) do             O(n)
    elem &lt;- extract-min(SH)           -&gt; O(logn)
    insert(BH, elem)                  -&gt; 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.