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

Question

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

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

Answer 2

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->left != NULL) {
    if (p->right == NULL || p->left->val > p->right->val) {
        p->val = p->left->val;
        p = p->left;
    } else {
        p->val = p->right->val;
        p = p->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)