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

I can suggest 2 choices to solve the problem, although neither performs a real update.

1. Use the priority_queue and push element each time you would like to update it. Accept the fact that you will have useless entries in the queue. When popping the top value, check if it contains the up-to-date value. If not, ignore it and pop the next.

   This way you delay the removal of the updated element until it comes to the top. I noticed this approach being used by top programmers realizing Dijkstra algorithm.

2. Use set. It is also sorted so you are able to extract the greatest element in logarithmic time. You are also able to remove the outdated element before inserting it again. So still no update operation possible, but removal and reinsertion is doable.

Seems like the complexity of both approaches is the same.