algorithm - 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.