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

Question

我正在尝试实现Prim的算法,为此我需要为优先级队列使用reduceKey方法(以更新优先级队列中的键值).我可以在STL优先级队列中实现吗？

如果它有帮助,这是我遵循的算法:

• 对于图G中的每个顶点u
  • 将你的关键设置为INFINITY
  • 将u的父级设置为NIL
• 将源顶点的键设置为0
• en-queue to priority queue Q图中的所有顶点,如上所示
• 而Q不是空的
  • 在Q中使用最低键弹出顶点u
  • 对于你做的每个相邻顶点v
    • if(v仍在Q中)和(key(u)+ weight-function(u,v)<key(v))然后
      • 设定你是v的父母
      • 更新v键等于键(u)+权重函数(u,v) //这部分给我带来问题,因为我不知道如何在优先级队列中实现reduceKey

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倍.当然,取决于数据.