C++ STL and the Lack of Update in Heap Implementation
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