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?