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