标签: decrease-key

我正在开发一个演示Djikstra算法的应用程序,并且要使用它,我需要在我的元素值减少时恢复堆属性.

关于复杂的问题是,当算法改变的元素的值,该元素的索引用于优先级队列中的内部结构(堆在这种情况下)是未知的.因此,我之前需要进行O(n)搜索,以便恢复索引,然后才能对其执行实际的减少键.

而且,我不确定操作所需的实际代码.我在这里使用D-Heap 作为我的优先级队列.伪代码会有所帮助,但我更喜欢Java中的一个例子,说明应该如何做.

许多快速优先级队列(例如Fibonacci堆和配对堆)支持减少键操作,该操作采用已存储在优先级队列中的元素并有效地降低其优先级.在Fibonacci和配对堆的情况下,reduce-key的执行速度比从优先级队列中删除元素并稍后重新插入要快.

我想知道在有序字典结构(二叉搜索树,跳过列表等)上是否可以支持类似的操作.具体来说,假设我有一个有序字典,并希望将某个键/值对的键更改为不同的键.是否可以在有序字典的任何标准表示中按时间O(1)或O(log log n)执行此操作？我很好奇,因为有了平衡的BST,这可以在O(log n)时间内通过删除元素并重新插入来完成,但似乎可能有更快的方法来做到这一点.

谢谢!

我正在尝试实现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

对于更新部分，

for all neighbors w of u:
    if dist[w] > dist[u] + l(u,w)
        dist[w] = dist[u] + l(u,w)
        prev[w] = u
        decreasekey(H,w)

这里，w是节点的ID，我认为它应该像pair(ID,key)，其中key是dist[ID]。如果是这样，在优先级队列中查找 ID 为 w 的节点应该花费 O(N) 时间，而不是 O(logN) 时间。那么，为什么Dijkstra算法中的decreasekey需要O(logN)时间呢？