Why finding the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?

Question

How we can prove that the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?

Is this useful that worst running time for comparison based sorting is >= longest path from root to leaf = height of the tree >= log(n!) = Ω(logn)?

• Ainsley H.: Otherwise you could sort in $o(n \log n)$ time.
• Ainsley H.: Please rewrite your question and be more precise. "the largest element [...] takes $\Omega(\log n)$ time" is not a valid statement.

Answer 1

Is this useful that worst running time for comparison based sorting is >= longest path from root to leaf = height of the tree >= log(n!) = Ω(logn)?

It is useful if we interpret $\log n!$ as $n \log n$.

How we can prove that the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?

It is possible if we interpret the operation as extracting instead of returning.

Extracting $n$ elements is equivalent to sorting $n$ elements, if sorting $n$ elements runs in $n \log n$ then sorting an element runs in $\log n$.

Answer 2

Probably you meant to extract the element. Also we are using a min-heap, so I would suppose you wanted to extract the smallest element, but the argument works for both.

Suppose you can extract minimal element from a binary min-heap in time $o(\log n)$. I claim that you can sort in time $o(n\log n)$, which contradicts a well known fact that in comparison based model sorting cannot be done faster than $O(n\log n)$.

Take elements $x_1,\ldots, x_n$, build a min-heap from them in time $O(n)$, then call extract_min $n$ times and append the minima to an auxiliary array. Observe that the last step takes $o(n\log n)$ time and the elements $x_i$ are sorted in the auxiliary array. Thus, you managed to sort in $o(n\log n)$ time which is impossible.