c++ - 在 STL 优先级队列 C++ 中实现 decreaseKey

Question

我正在尝试实现 Prim 算法，为此我需要为优先级队列设置一个 decreaseKey 方法(以更新优先级队列中的键值)。我可以在 STL 优先级队列中实现它吗？

如果有帮助，这是我正在遵循的算法:

• 对于图G中的每个顶点u
  • 将 u 的键设置为 INFINITY
  • 将你的父级设置为 NIL
• 将源顶点的键设置为0
• 使用上述键将图中所有顶点入队到优先级队列 Q
• 当Q不为空时
  • 用Q中最低的键弹出顶点u
  • 对你的每个相邻顶点v做
    • 如果 (v 仍在 Q 中) 和 (key(u) + weight-function(u, v) < key(v)) then
      • 设置你为v的父级
      • 将 v 的键更新为相等的键(u) + 权重函数(u, v) //这部分给我带来了问题，因为我不知道如何在优先级队列中实现 decreaseKey<

Answer 1

我不认为你可以在 STL 容器中实现它。请记住，您始终可以基于 vector 编写自己的堆(优先级队列)，但有一个解决方法:

保留你的距离数组，比方说d。在您的优先级队列中，您放置了成对的距离和该距离的顶点索引。当你需要从队列中删除一些值时，不要删除它，只需更新 d 数组中的值并将新对放入队列即可。

每次从队列中获取新值时，检查成对的距离是否真的那么好，就像在数组 d 中一样。如果不是忽略它。

时间是相同的 O(MlogM)。内存是 O(MlogM)，其中 M 是边数。

还有另一种方法:使用RB-Tree，它可以在O(logN) 中插入和删除键并获得最小值。您可以在 std::set 容器中找到 RB-Tree 的 STL 实现。

但是，虽然时间复杂度相同，但 RB-Tree 运行速度较慢且隐藏常量较大，因此它可能会稍微慢一些，appx。慢了5倍。当然要看数据。