# Extract Max for a max-heap in $\log n + \log\log n$

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).

-

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".

-
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