CODEWITHSUNDEEP
c++stlheap
Jake
Jake

Reputation: 2907

Implementing Decrease Key with STL heap in O(logn) time

At the moment STL Heap does not support decrease key, however one can just change the value on the vector directly and call make_heap again which is O(n) time. However that's not as efficient as a binary heap decrease key which would take O(logn) time.

Is there a way to achieve O(logn) time using STL heap functions?

Upvotes: 9

Views: 5619

Answers (2)

Alan Stokes
Alan Stokes

Reputation: 18974

I'm pretty sure there's no standard-conforming way of doing it - Wikipedia says so too:

there is no standard support for the decrease/increase-key operation

Although it does go on to point to the gheap library, which might well be worth a look.

The problem here is that the standard does not mandate what form the heap structure takes, nor how exactly the operations are performed. (In general this is a good thing.)

If the implementation is using a standard binary heap then I think you can simply decrease the element at heap[i] and then call push_heap(heap.begin(), heap.begin() + i + 1), which will do the necessary up-heap operation. The element that ends up at position i must have been no larger than the value there originally, and so the heap property of the whole heap is preserved. But this is not supported by the standard even if it does work sometimes in some implementations.

Upvotes: 5

Mankarse
Mankarse

Reputation: 40633

You can use pop_heap followed by decrementing the value followed by push_heap:

int main() {
    //Create the heap
    std::vector<int> heap{1,2,3,4,5,6,7};
    std::make_heap(heap.begin(), heap.end());

    //Decrease key
    std::pop_heap(heap.begin(), heap.end());
    --*(std::prev(heap.end()));
    std::push_heap(heap.begin(), heap.end());
}

EDIT: Is this what you mean, or do you want to be able to decrease the key of any element in the heap?

Upvotes: 1

Related Questions