Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Given a max heap with extract-max operation.

The basic version takes $2 \log n$ steps. How can I make it in $\log n + \log\log n$ and how in $\log n + \log\log\log n $?

I thought of putting $-\infty$ on the heap root but not really sure what to do with it as it can go anywhere.

To be more precise, steps are considered only compares between array item values. I'm reading CLRS Chapter 6 (MAX-HEAPIFY and HEAP-EXTRACT-MAX).

share|improve this question

1 Answer 1

Elmasry et al. discuss reducing the number of comparisons for extract-max to $\log n + o(\log n)$ in "A Framework for Speeding Up Priority-Queue Operations". See also Elmasri's "Layered Heaps", Edelkamp et al.'s "Two Constant-Factor-Optimal Realizations of Adaptive Heapsort", Carlsson's "An optimal algorithm for deleting the root of a heap", and Gonnet and Munro's "Heaps on heaps".

share|improve this answer
iv read parts of the article and I didn;t udertand how to solve the problem –  Nahum Litvin Nov 19 '12 at 15:02
If you ask a more specific question, like "In section 4.2, the authors say that they build an atomic binomial heap. Where is that defined?" someone might be able to help you. –  jbapple Nov 19 '12 at 18:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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