Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to do an efficient priority update in STL priority_queue?

People also ask

How is priority queue implemented in STL?

The priority queue in the STL of C++ is a dynamically resizing container to implement the special case of priority queye under the queue data structure. It is a sequential linear container. The top element of the priority queue is the greatest with all elements arranged in non-increasing order.

Which is faster priority queue or set?

So to convert your priority queue from max heap to min heap you can insert negative distance like I did here. Or you can use greater as mentioned here. Here is the diff from your TLE code. PS - priority queue is 30 times faster than set.

How do you structure a priority queue?

Begin Define a structure of type student. Initialize variables in student structure. Define another structure of type comparemarks Overload the variables of student structure in comapremarks structure. Use priority queue with structure.

Is priority queue in STL?

In C++, the STL priority_queue provides the functionality of a priority queue data structure. A priority queue is a special type of queue in which each element is associated with a priority value and elements are served based on their priority.


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.


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.


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


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.


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