Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.