# Complexity of using Extract-Max to extract n/2 elements from a max-heap with n distinct elements

I've been given the following question and I've been finding it hard to give a good answer:

Prove or disprove: given a max-heap with n distinct elements, using Extract-Max to extract n/2 of the elements takes Ω(nlogn) time.

Because the heap contains distinct elements, I'm lead to believe the claim is true: I've tried to create heaps with distinct elements such that Extract-Max would take O(1) for n/2 extractions, but just couldn't do it. So, in order to prove the claim, I've tried to prove another claim that could help - that in a heap with distinct elements, Extract-Max would take Ω(logn) except for maybe the first few times, but couldn't prove it either.

Does anyone have a nice way to prove/disprove this?

• Check what happens when the starting heap is complete and everything on the bottom level is smaller than everything not on the bottom level. – Louis Apr 25 '14 at 13:36
• Hi Louis! I've checked and in your case Extract-Max takes Ω(logn) each time. If done n/2 times, it takes Ω(nlogn). So, this doesn't disprove or prove the claim, it is just an example. Or, am I missing something? – user3572814 Apr 25 '14 at 19:35
• The general case of a heap with distinct elements doesn't mandate that everything on the bottom level is smaller than everything not on it - for example, elements on the bottom level of the left branch can be bigger than some of the elements on the right branch (even those not on the bottom). – user3572814 Apr 25 '14 at 20:21
• Yes, but the existence of a well-formed max-heap that forces $\Omega(n\log n)$ operations gives you the lower bound you want. – Louis Apr 26 '14 at 12:17
• But what about heaps in which not everything on the bottom level is smaller than everything not on the bottom level? I need to prove a lower bound for any heap that has distinct elements, not just for the type of heap you suggested. – user3572814 Apr 26 '14 at 12:47