I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS:

Exercise 6.4-5
Show that when all elements are distinct, the best-case running time of heapsort is $\Omega(n\text{log}(n))$.

I've been thinking over this for about a day or so, and so far I've tried working with finding the time it takes run heapsort through just the leaves of a heap (I've been focusing on full heaps with $n = 2^h - 1$ elements), but couldn't draw any conclusions except for the minimum and 2nd-minimum elements, so that hasn't really gotten anywhere.

Does anyone have any hints as to how to proceed? Please don't post solutions to the problem, just hints/potential directions to proceed.

Any help is much appreciated!


keep in mind, that a heap has a height of $O(\log n)$ and its root contains the minimal element. how long does it take to restore the heap if you remove the root element (the minimum!) and how often you have to do this in order to achieve a sorted list?

after that, think of the time you need for building a heap out of $n$ elements in abitrary order

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.