A friend asked me some time ago if the implementation of the heap data structure in the STL has update functions. He couldn’t find any documentation about an update_heap() function. He was as sure as I was (some time ago) that there must be one, but he can’t find it. I can understand him.
It is true that was STL gives you is just push_heap() and pop_heap(). There is no way to update the heap. Since heap is commonly used for priority queues I expected it to have update functionality implemented. I find it quite restrictive to have a priority queue where the priority of an item can’t change!
The good thing is that I had the problem before so I was able to present him a solution instantly. Some time ago I implemented some templetized update_heap() function. The implementation is such that blends smoothly with the STL. The syntax of update_heap() is :
void update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval)
or if you need to supply a compare functor :
void update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval, CPred pred)
I open-sourced my heap update implementation since to me is very funtamental to have an update function for heaps. You can download the code from here. The source is released under the GPL.
I hope you find the source usefull!
STL, C++, Heap