Hi,

It is indeed suprising to see that STL doesn’t provide an algorithm to adjust one value of the heap. OTOH, i never needed it before :) Luckely, the STL is set up as such that it can easily be expanded. Though if you do, I suggest you stick to standard STL functions. The problem in this case is _Dist_type and _Val_type. Although probably provided by the STL you’re using, these are by no means standard provided functions. So, if you try to use it with another implementation, it may possible break. AFAIK, the best change you have is to use iterator_traits to get these values. I also wondered why you pass newval by pointer to update_heap. a constant reference seems more suitable to me, or why not - to use the same spirit as the other heap functions - let the client update the iterator before calling update_heap. (and on the nitpicking side: it’s best to avoid leading underscores ;) )

Bramz

It is true that was STL gives you is just push_heap() and pop_heap() to manipulate heaps. 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!

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)

For my blog post about this code check this link.