1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Check what happens when the starting heap is complete and everything on the bottom level is smaller than everything not on the bottom level. $\endgroup$ – Louis Apr 25 '14 at 13:36
  • $\begingroup$ 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? $\endgroup$ – user3572814 Apr 25 '14 at 19:35
  • $\begingroup$ 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). $\endgroup$ – user3572814 Apr 25 '14 at 20:21
  • $\begingroup$ Yes, but the existence of a well-formed max-heap that forces $\Omega(n\log n)$ operations gives you the lower bound you want. $\endgroup$ – Louis Apr 26 '14 at 12:17
  • $\begingroup$ 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. $\endgroup$ – user3572814 Apr 26 '14 at 12:47

Your Answer

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

Browse other questions tagged or ask your own question.