Extract Max for a max-heap in $\log n + \log\log n$ comparisons 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).
Explanation for log n + log log n comparisons:

1) First, remove the max element from the heap, leaving a hole at the root.

2) Next, remove the last element of the heap (at the bottom right), and hold it in a temp.

3) Reconstruct the heap by iteratively replacing the hole with the greater of its 2 children.  This loop takes log n comparisons (comparing the children at each level of the tree).  Here is an example implementation:

p = root;
while (p-&gt;left != NULL) {
    if (p-&gt;right == NULL || p-&gt;left-&gt;val &gt; p-&gt;right-&gt;val) {
        p-&gt;val = p-&gt;left-&gt;val;
        p = p-&gt;left;
    } else {
        p-&gt;val = p-&gt;right-&gt;val;
        p = p-&gt;right;
    }
}


4) Now, you have a hole at the bottom of the heap, and you have an element that you removed in step #2.  Insert the element into the hole.  This element needs to be fixed because it could be greater than its parent.

5) Fix the heap in log log n time.  Where you inserted the element, if you take all of its parents, it forms a sorted list of log n elements.  You can do a binary search to find the correct position of the inserted element in this list of parents.  This takes log log n comparisons (binary search in a log n list).  Once you find the position, you can insert the element in the correct place, moving the rest of the elements down.

Total number of comparisons: log n (step 3) + log log n (step 5)