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 hope you find the source usefull!