java - 本机库中的减键/增键支持

Question

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

Answer 1

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

• 已经拥有对包含该元素的堆节点的引用。这意味着您必须公开内部堆表示的细节，限制您的实现选项（您不能像传统表示那样使用直接数组），并且通常会使您的 API 更难使用。
• 维护一个HashMap或类似的将每个元素指向其在堆中的位置。在用户不修改密钥的情况下，这会产生很大的开销。

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