Easiest way of using min priority queue with key update in C++

Question

Sometimes during programming contests etc., we need a simple working implementation of min priority queue with decrease-key to implement Dijkstra algorithm etc.. I often use set< pair<key_value, ID> > and an array (mapping ID-->key_value) together to achieve that.

• Adding an element to the set takes O(log(N)) time. To build a priority queue out of N elements, we simply add them one by one into the set. This takes O(N log(N)) time in total.

• The element with min key_value is simply the first element of the set. Probing the smallest element takes O(1) time. Removing it takes O(log(N)) time.

• To test whether some ID=k is in the set, we first look up its key_value=v_k in the array and then search the element (v_k, k) in the set. This takes O(log(N)) time.

• To change the key_value of some ID=k from v_k to v_k', we first look up its key_value=v_k in the array, and then search the element (v_k, k) in the set. Next we remove that element from the set and then insert the element (v_k', k) into the set. We then update the array, too. This takes O(log(N)) time.

Although the above approach works, most textbooks usually recommend using binary heaps to implement priority queues, as the time of building the binary heaps is just O(N). I heard that there is a built-in priority queue data structure in STL of C++ that uses binary heaps. However, I'm not sure how to update the key_value for that data structure.

What's the easiest and most efficient way of using min priority queue with key update in C++?

Answer 1

Although my response will not answer the original question, I think it could be useful for people who reach this question when trying to implement Dijkstra algorithm in C++/Java (like myself), something that was comment by the OP,

priority_queue in C++ (or PriorityQueue in Java) do not provide a decrease-key operation, as said previously. A nice trick for using those classes when implementing Dijkstra is using "lazy deletion". The main loop of Dijkstra algorithm extracts the next node to be processed from the priority queue, and analises all its adjacent nodes, eventually changing the cost of the minimal path for a node in the priority queue. This is the point where decrease-key is usually needed in order to update the value of that node.

The trick is not change it at all. Instead, a "new copy" for that node (with its new better cost) is added into the priority queue. Having a lower cost, that new copy of the node will be extracted before the original copy in the queue, so it will be processed earlier.

The problem with this "lazy deletion" is that the second copy of the node, with the higher bad cost, will be eventually extracted from the priority queue. But that will be always occur after the second added copy, with a better cost, has being processed. So the very first thing that the main Dijkstra loop must do when extracting the next node from the priority queue is checking if the node has being previously visited (and we know the shortest path already). It is in that precise moment when we will be doing the "lazy deletion" and the element must be simply ignored.

This solution will have a cost both in memory and time, because the priority queue is storing "dead elements" that we have not removed. But the real cost will be quite small, and programming this solution is, IMHO, easier than any other alternative that tries to simulate the missing decrease-key operation.

Answer 2

Well, as Darren already said, std::priority_queue doesn't have means for decreasing the priority of an element and neither the removal of an element other than the current min. But the default std::priority_queue is nothing more than a simple container adaptor around a std::vector that uses the std heap functions from <algorithm> (std::push_heap, std::pop_heap and std::make_heap). So for Dijkstra (where you need priority update) I usually just do this myself and use a simple std::vector.

A push is then just the O(log N) operation

vec.push_back(item); std::push_heap(vec.begin(), vec.end()); 

Of course for constructing a queue anew from N elements, we don't push them all using this O(log N) operation (making the whole thing O(Nlog N)) but just put them all into the vector followed by a simple O(N)

std::make_heap(vec.begin(), vec.end()); 

The min element is a simple O(1)

vec.front(); 

A pop is the simple O(log N) sequence

std::pop_heap(vec.begin(), vec.end()); vec.pop_back(); 

So far this is just what std::priority_queue usually does under the hood. Now to change an item's priority we just need to change it (however it may be incorporated in the item's type) and make the sequence a valid heap again

std::make_heap(vec.begin(), vec.end()); 

I know this is an O(N) operation, but on the other hand this removes any need for keeping track of an item's position in the heap with an additional data structure or (even worse) an augmentation of the items' type. And the performance penalty over a logarithmic priority update is in practice not that signficant, considering the ease of use, compact and linear memory useage of std::vector (which impacts runtime, too), and the fact that I often work with graphs that have rather few edges (linear in the vertex count) anyway.

It may not in all cases be the fastest way, but certainly the easiest.

EDIT: Oh, and since the standard library uses max-heaps, you need to use an equivalent to > for comparing priorities (however you get them from the items), instead of the default < operator.