can we use heapsort to sort an unordered set of numbers in linear time?

Question

Hey guys quick question..

As we know that, we can build a heap from an unordered set of numbers in linear time. can anyone prove how?

Thanks in Advance !

Answer 1

No.

Although you can build a heap (presumably implemented as a complete binary tree) in linear (O(n)) time, each extraction from the heap takes O(log(n)) time in order to maintain the heap invariant. Thus, the assembly of the sorted array from the binary heap takes O(n log(n)) time total, just as all optimal binary comparison-based sorting algorithms do.