java - native 库中减少键/增加键支持

Question

我注意到 Java 中堆的大多数默认实现(PriorityQueue、Guava MinMaxPriorityQueue 等)和 Python (heapq) 不支持 CLRS 中描述的增加键/减少键操作。对于堆。但是，我还没有找到关于为什么会这样的解释。有谁知道/文档中某处描述了基本原理吗？

Answer 1

要修改堆中特定元素的键，您的选择基本上是:

• 已经拥有对包含该元素的堆节点的引用。这意味着您必须公开内部堆表示的详细信息，限制您的实现选项(您不能像传统表示那样使用直接数组)，并且通常会使您的 API 更难以使用。
• 维护一个HashMap或类似的东西，将每个元素定向到其在堆中的位置。如果用户不修改 key ，这会产生大量开销。

此外，Java Comparator 期望是无状态的——比较操作对于相同的输入应该始终具有一致的输出——并且在大多数算法中很少使用修改键，并且很少严格必要需要使用优先级队列。