问题标签 [decrease-key]

许多快速优先级队列（例如斐波那契堆和配对堆）支持减少键操作，该操作采用已存储在优先级队列中的元素并有效地降低其优先级。在斐波那契和配对堆的情况下，减少键的执行速度比从优先级队列中删除元素并稍后重新插入它要快。

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

谢谢！

我正在尝试实现 Prim 算法，为此我需要为优先级队列提供 reductionKey 方法（以更新优先级队列中的键值）。我可以在 STL 优先级队列中实现这个吗？

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

• 对于图 G 中的每个顶点 u
  • 将 u 的键设置为 INFINITY
  • 将你的父级设置为 NIL
• 将源顶点的键设置为 0
• 排队到优先级队列 Q 图中所有顶点与上面的键
• 而 Q 不为空
  • 弹出 Q 中键最低的顶点 u
  • 对于你的每个相邻顶点 v
    • 如果 (v 还在 Q) 并且 (key(u) + weight-function(u, v) < key(v)) 那么
      • 将 u 设置为 v 的父级
      • 将 v 的键更新为等于 key(u) + weight-function(u, v) // 这部分给我带来了问题，因为我不知道如何在优先级队列中实现 reduceKey

I am working on an application that demonstrates the Djikstra's algorithm, and to use it, I need to restore the heap property when my elements' value is decreased.

The problem regarding the complexity is that when the algorithm changes the value of an element, that element's index in the internal structure (heap in this case) used for the priority queue is unknown. As such, I currently need to do an O(n) search, in order to recover the index, before I can perform an actual decrease-key on it.

Moreover, I am not exactly sure about the actual code needed for the operation. I am using the D-Heap here for my Priority Queue. Pseudocode would help, but I would prefer an example in Java on how this should be done.

如何在斐波那契堆上的递减键操作中获得 O(1) 摊销复杂度？仅使用 BFS 在斐波那契堆中找到包含该元素的节点需要 O(n) 时间，这应该使得不可能获得 O(1) 摊销时间。

作为参考，这是我搜索相关节点的 BFS 实现：

这是我的减少键代码：

二项式堆递减键的《算法导论》一书提供的接口是：BINOMIAL-HEAP-DECREASE-KEY (H,x,k)，其中H是指向树的第一个根的指针，x是节点的“索引”，其键将减少到 k。时间复杂度为 O(logn)

但是，我们通常使用链表来实现二项式堆，其中不执行搜索就无法直接访问 x，通常为 O(n)。

解决此问题的一种方法是为二项式堆中的每个节点保留一个指针，然后直接访问 O(1) 中的每个节点，但空间复杂度为 O(n)。

有人知道更好的解决方案吗？谢谢！

可以在此处找到先前的讨论。

对于更新部分，

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

我试图在我的实现中使用来自 boost 的斐波那契堆，但是我的程序崩溃了，当我调用 reduce 函数时，这个例子（W 是一个简单的类）：

我想知道为什么 Java 的优先级队列不支持 ChangePriority。我在某处（没有详细信息）读到，放弃 ChangePriority 允许人们使用更有效的实现，但不知道它怎么可能——二进制堆似乎非常简单/高效的数据结构——看不到任何改进的空间。另一个线索可能是它可能需要笨拙的界面来向 PQ 指示哪个元素（可能是堆中的位置）改变了它的优先级，但我仍然是 Java 的新手，无法得出结论。

编辑：为什么这不是一个毫无意义的问题？如果您是 Java 新手（尤其是 C/C++ 背景），您会开始想知道所有指针都去了哪里，或者我如何在 Java 中实现 Dijkstra 等。

第一个问题已经回答了很多次，据我所知，第二个问题没有一个简单的答案。人们可以期望，在像 Java 这样的语言中，所有常用的编程工具都在手边，开箱即用，封装在一个漂亮的类包装器中。但是突然之间你必须自己实现一个带有减少键方法的 PQ，这在 Java 中可能比在 C/C++ 中更尴尬。在这个问题中，我不是在问如何实现 Dijkstra（这在其他一些线程中得​​到了很好的回答）。如果没有减少键/优先级方法，仍然可能有许多 PQ 应用无法解决，例如。如果优先级更新比 PQ 中的项目多得多。在 Dijkstra 中最多有 V

因此，人们可能会认为 Java 的 PQ 缺乏变更优先级是有一些严重的原因的。不管实际的 Java 的 PQ 接口如何，这些原因本身可能很有趣。

我正在寻找二项式堆的 Python 实现，我注意到代码没有实现 reduceKey。为什么在二项式堆中没有人实现 reduceKey？

Tomcat 在虚拟机中运行。我监测到 JVM 提交的堆内存从 4G 突然减少到 3.86G。这会导致 FULL GC。我想知道JVM为什么以及何时这样做？