c++ - 您如何更新priority_queue中的值，或者是否有另一种方法可以在c++中更新堆中的键

Question

当我注意到时，我正在研究 Djikstra 的算法，我可以在 O(logn) 时间内更新堆中的键(使用 n 个键)(pseudocode 中的最后一行)。如何在 C++ 中更新堆中的键，priority_queues 中是否有任何方法可以做到这一点？还是我必须编写自己的堆类才能像这样在 O(logn) 中实现更新？

编辑 1:
澄清我的需求 - 对于具有 n 个元素的二进制堆 -
1) 应该插入新值并在 O(logn) 中找到并弹出最小值
2) 应该更新 O(logn) 中已经存在的键

我试图想出一种方法来使用 make_heap、push_heap、pop_heap 和 John Ding 建议的自定义更新函数来实现这一点。

但是我在制作函数时遇到了问题，我首先需要在堆中找到键的位置。在堆中的 O(logn) 下执行此操作需要查找数组以查找堆中键的位置，see here (我不知道任何其他方式)。但是，当我调用 push_heap 或 pop_heap 时，这些查找表不会更新。

Answer 1

您可以使用 priority_queue 优化 dijktra 算法.它由二叉堆实现，您可以在其中弹出顶部或插入 O(logN) 中的元素时间。但是，由于 priority_queue 的封装，你不能修改任何元素的key(更准确地说是减少key)。
所以我们的方法是将多个元素插入堆中，而不管我们是否有多个元素引用同一个节点。
例如，当Node N : distance = 30, GraphNode = A (其中 A 指的是图中的一个节点，而 N 是堆中的一个节点)
已经在堆中，然后使用 priority_queue当我们尝试放松节点 N 时，无法帮助您进行这样的操作:decrease_key_to(N, 20)通过减少键可以使堆总是包含少于 N 个元素，但它不能由 priority_queue 实现
我们可以用它做的是在堆中添加另一个节点:

Node N2 : distance = 20, GraphNode = A
push N2 into the heap

对应于 priority_queue::push所以你可能需要实现一个支持 decrease_key 的二进制堆。自己或在线查找实现，并存储指向堆中每个元素的指针表，以了解通过图中的节点访问元素。
作为扩展，使用斐波那契堆甚至可以使 decrease_key更快，那是Dijkstra的终极水平，哈哈:)

我的答案的最后一个版本的问题:
我们无法使用 push_heap 定位插入堆的元素.