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

Question

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?

Answer 1

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.