How to do an efficient priority update in STL priority_queue?

1800_INFORMATION_3146 0
Viewed 45727

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?

priority-queue stl c++
7 Answers

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.

Admin1

I have implemented a high-performance updatable priority queue and made it available on github.

This is how you would typically use it :

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

To complement Jarekczek's answer, if indeed both the set and "pure heap with useless entries" approaches have the same complexity, the stl::set version typically performs much slower than the stl::priority_queue version due to the fact that it is implemented with red-black trees that only guarantee their depth to be lower than 2*log_2(n_elements) and require regular updates, while stl::priority_queue is an as pure and fast binary heap as possible. This is why it is typically used when implementing Dijkstra.

The set approach may however be faster when making a lot of updates on few base nodes. This is also where using my library would bring you the most improvement.

user_37996090

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

user_2679040

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

user_776730
Related