在 C++ 中使用带密钥更新的最小优先级队列的最简

问题描述

有时在编程竞赛等期间，我们需要一个带有减少键的最小优先级队列的简单工作实现来实现 Dijkstra 算法等.我经常使用 set<;对<key_value, ID>>和一个数组(映射 ID-->key_value)来实现这一点.

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.

• 向集合中添加元素需要 O(log(N)) 时间.为了用 N 个元素构建一个优先级队列，我们​​只需将它们一个一个地添加到集合中.这总共需要 O(N log(N)) 时间.

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

具有最小 key_value 的元素只是集合的第一个元素.探测最小元素需要 O(1) 时间.删除它需要 O(log(N)) 时间.

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.

为了测试某个ID=k是否在集合中，我们首先在数组中查找它的key_value=v_k，然后在集合中查找元素(v_k, k).这需要 O(log(N)) 时间.

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.

要将某个ID=k的key_value从v_k改为v_k'，我们首先在数组中查找它的key_value=v_k，然后在集合中查找元素(v_k, k).接下来，我们从集合中删除该元素，然后将元素 (v_k', k) 插入到集合中.然后我们也更新数组.这需要 O(log(N)) 时间.

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.

虽然上述方法有效，但大多数教科书通常建议使用二叉堆来实现优先级队列，因为构建二叉堆的时间仅为 O(N).听说C++的STL里有内置的优先级队列数据结构，使用的是二进制堆.但是，我不确定如何更新该数据结构的 key_value.

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.

在 C++ 中使用带密钥更新的最小优先级队列的最简单和最有效的方法是什么?

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

推荐答案

虽然我的回答不会回答最初的问题，但我认为这对尝试在 C++/Java 中实现 Dijkstra 算法时遇到这个问题的人可能有用(像我一样)，OP 评论的内容，

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(或 Java 中的 PriorityQueue)不提供 decrease-key 操作.在实现 Dijkstra 时使用这些类的一个很好的技巧是使用延迟删除".Dijkstra 算法的主循环从优先队列中提取下一个要处理的节点，并分析其所有相邻节点，最终改变优先队列中某个节点的最小路径成本.这是通常需要 decrease-key 以更新该节点的值的点.

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.

这种懒惰删除"的问题在于，节点的第二个副本，具有更高的坏成本，最终会从优先级队列中提取出来.但这将始终发生在第二个添加的副本(成本更高)被处理之后.所以在从优先级队列中提取下一个节点时，主 Dijkstra 循环必须做的第一件事是检查该节点之前是否被访问过(并且我们已经知道最短路径).正是在那个精确的时刻，我们将进行懒惰删除"并且必须简单地忽略该元素.