Average time complexity for a removal from minheap

Question

The average time complexity to remove (i.e. removeMin on a min-heap) all elements on heap in order ???

Answer 1

The question is essentially about heapsort -- building a min heap, and then removing elements one at a time to produce a sorted list. Building the min heap is O(N), and this cost will turn out to be dominated by the cost of extracting the elements.

The worst case for the extraction phase of heapsort is relatively easy -- each removal is O(log N) and there's N of them, so the complexity must be O(N log N).

This doesn't mean the average is O(N log N). For that, we need Lower bound on heapsort? to show something more difficult -- namely, that the best case complexity for the extraction phase is also Theta(N log N).

The average must be between the best (Theta(N log N)) and worst (O(N log N)) cases, so is Theta(N log N).