Arch Linux

davvil

Member

Registered: 2008-05-06

Posts: 165

[C++] std::update_heap functionality?

In my programm I have a priority queue where the objects themselves are more or less static and stored as pointers, but the priorities change in the course of the program. I would like to have a function to say "this element in the queue has changed its priority" and update the queue accordingly. I have searched in the stl but neither the priority_queue class nor the make_heap function(s) provide this functionality, only pop/push interface. Googling provides some answers, but none really satisfying:

- Using boost: It has some class that provides this functionality, but I would rather stay away from some extra dependencies for such a small functionality addon.
- http://blog.smellthedata.com/2009/08/mu … es-to.html I encounter a memory bound problem, as reported in http://www.ics.uci.edu/~yanbinl/ (section Software). However when I use this second implementation it seems stuck in an endless loop
- http://www.devmaster.net/forums/showthread.php?t=3998 I do not get it compiled (how I love compiler errors for templates...), even after some corrections in the code I was able to find.

At the moment I just call make_heap again on the vector containing the elements, but this is surely overkill and the operation is frequent enough to pay off trying to optimize it. Does anyone know of a working implementation?

tavianator

Member

From: Waterloo, ON, Canada

Registered: 2007-08-21

Posts: 858

Website

Re: [C++] std::update_heap functionality?

Um, I don't think any of the performance benefits of a specialised priority queue data structure apply if the priorities are not constant.  But I can think of one reasonably fast implementation using only the STL: an std::multimap<int, Object*>.  The lowest priority object can be accessed with map.begin()->second (and the highest with map.rbegin()->second), in O(1) time.  Insertion/removal is O(lg n).  Changing the priority just means an insertion and a removal, so it's O(lg n) too.

davvil

Member

Registered: 2008-05-06

Posts: 165

Re: [C++] std::update_heap functionality?

Well, the priorities are constant until the point I change them, when I notify the corresponding structure. It would be equivalent of a pop followed of a push of the same object with the updated priority.

I hadn't thought about the multimap solution, I didn't know that the specification fixes that it must be a sorted container. I expect using it would be very similar to using a priority_queue with the pop/push operation pair, won't it?

tavianator

Member

From: Waterloo, ON, Canada

Registered: 2007-08-21

Posts: 858

Website

Re: [C++] std::update_heap functionality?

Well kind of, but only if you only ever update the priority of the highest-priority object.  If that's true, then just use a priority_queue.