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

Problem Detail: 

Given a max heap with extract-max operation.

The basic version takes $2 \log n$ comparisons. How can I make the running time just $\log n + \log\log n$ comparisons? How about $\log n + \log\log\log n $ comparisons?

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, I'm only counting comparisons between array item values. I'm reading CLRS Chapter 6 (MAX-HEAPIFY and HEAP-EXTRACT-MAX).

Asked By : Nahum

Answered By : jbapple

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6698