How to do an efficient priority update in STL priority_queue?

Question

I have a priority_queue of some object:

typedef priority_queue<Object> Queue;
Queue queue;

From time to time, the priority of one of the objects may change - I need to be able to update the priority of that object in the queue in an efficient way. Currently I am using this method which works but seems inefficient:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

I implemented it this way because I was in kind of a hurry at the time and this was the quickest thing I could do that I could be sure it would work ok. There has to be a better way than this though. Really what I want is a way to either:

• extract out the instance with the changed priority and insert a new one with the new priority value
• update the instance with the changed priority and then update the queue so that it is correctly sorted

What is the best way to do this?

Answer 1

You may want to have a look at replace_if with an example here.

Answer 2

I think you are out of luck with standard priority queue because you can't get at the underlying deque/vector/list or whatever. You need to implement your own - it's not that hard.

Answer 3

The most straightforward way to do this with STL (that I know) is to remove the entry, update its priority and then reinsert it. Doing this is quite slow using std::priority_queue, however you can do the same thing with std::set. Unfortunately you have to be careful to not change the priority of an object when it is in the set.

I have implemented a mutable_priority_queue class based gluing together an std::multimap (for priority to value mapping) and an std::map (for value to priority mapping) that allows you to insert/remove items as well as update existing values in logarithmic time. You can get the code and an example of how to use it here

Answer 4

The appropriate data structure is called "Fibonacci Heap". But you need to implement it yourself. Insert/Updates are O(1) ExtractMin is O(logn)