An Updateable Priority Queue

There are a number of algorithms which use priority queues to schedule operations but which need to be able to update the priorities of items in the queue as operations are performed. Two examples are the Fast-Marching Method and Mesh Simplification algorithms, which greedily remove the lowest cost item from a queue, perform an operation and then update the costs of geometrically nearby items. Although the STL specification provides priority queue and heap data structures, it is not straightforward to efficiently update priorities of items that are already in the queue.

One option is to use a std::multiset and augment the stored data with a priority field. Min(), Insert(), Delete() and Update() can then be performed in logarithmic time, which is pretty reasonable in most cases. Updating the position of a value in the queue then consists of removing the item from the queue, updating the priority value and then adding the item back to the queue. This works fine in practice, but has some drawbacks. First you need to ensure that the priority field is never changed when the data is actually in the queue, i) since this would destroy the ordering of the queue and ii) probably generate a run-time error in the stl::multiset implementation. Secondly if you want to use the same data in multiple queues, you need multiple priority fields and/or multiple comparison predicates which cause code bloat and an increased memory footprint even when you're not using the queues.

Another option (and the one taken here) is to stitch together two std::maps. One map provides an ordered mapping from priorities to data and the other provides the reverse mapping. The basic sequence of operations of removing an item, updating its priority and then reinserting it remains, except that since the maps own their own data, there is no concern of a user modifying the priorities arbitrarily. Also, when the queue is no longer needed, the additional memory required for its operation is freed and no extra data fields are littering up the data structures. The one condition is that both the priorities AND queued values must have an ordering. If you're storing data as pointers this comes for free, but if you're storing data by value in the queue then you will need to define a comparison predicate. However, this predicate can be reused among ALL priority queues.

I've called the class a mutable_priority_queue, and it shares similarities with both std::map and std::priority_queue. In order to ensure that the mappings don't become polluted, access to the stored data is quite restricted. The primary methods that can be used are push/insert, pop/delete and update. In order traversal is also possible using iterators, however the values stored in the queue cannot be modified through these iterators.

#include<iostream>
#include"mutable_priority_queue.h"

int main( int argc, char **argv ){
 mutable_priority_queue<float,int> A;
 mutable_priority_queue<float,int>::iterator i;

 A.insert( 1,  0.0f );
 A.insert( 2,  2.0f );
 A.insert( 3, -1.0f );

 std::cout << "A:" << std::endl;
 for( i=A.begin(); i!=A.end(); i++ ){
  std::cout << "key: " << i->first << ", value: " << i->second << std::endl;
 }

 A.update( 2, -5.0f );
 std::cout << "A:" << std::endl;
 for( i=A.begin(); i!=A.end(); i++ ){
  std::cout << "key: " << i->first << ", value: " << i->second << std::endl;
 }
 return 0;
}

Operations are logarithmic in the number of stored items and about 2X slower than std::map on its own (not surprising since two maps are used). So if your application performs a reasonable amount of processing outside of queue operations it should be more than sufficient.

You can get the code for the queue and a slightly more complex example below:
mutable_priority_queue.h
priority_queue_example.cpp