Java 的 PriorityQueue 显示添加了更高优先级的重复键的意外行为

Question

我试图使用 PriorityQueue class 作为优先级队列来实现 Djikstra 算法的一个稍微修改的版本。我遇到了一种奇怪的行为，我无法在任何地方找到解释。我怀疑这种行为，但想知道其他人对此有何看法。有人可以解释为什么 PriorityQueue 的行为如下所示：

由于标准算法涉及在 'relax' 操作期间降低节点的权重，这意味着获取节点的句柄并降低其权重（我知道您使用以下方法备份队列哈希图，但这是一个实验）。此方法涉及简单地将节点的另一个副本添加到 PriorityQueue 中。节点处理一次后，重复项将被忽略。然而，这种实现的问题是 PriorityQueue 对于随后添加的重复项以未定义的方式运行。这是显示相同内容的片段：

import java.util.PriorityQueue;
public class PriorityQueueTest {
    public static void main(String[] args) {
        int[] weight = new int[]{1, 2, 3};

        PriorityQueue<Integer> pq = new PriorityQueue<>(weight.length, (a, b) -> weight[a] - weight[b]);        
        for(int i=0; i<3; i++)
            pq.add(i);

        //change weight of node '1' from 2 to 0
        weight[1] = 0;
        //add duplicate node '1'. Note that this time weight 0 by the comparator.
        pq.add(1);

        while(!pq.isEmpty())
            System.out.println(pq.remove());
    }    
}

随着节点“1”的权重降低，其优先级随之提高，人们会期望节点按以下顺序被删除：

但实际结果不同：

另请注意，如果我只使用节点 0 和 1（将上面的 for 循环更改为

for(int i=0; i<2; i++)

), 然后是

的预期顺序

1
1
0

与实际订单相同！

您可以尝试添加更多节点并更改其他一些节点的权重，这有时会再次出现这种意外行为，具体取决于第一次复制后添加的节点数。

我怀疑是在添加副本时，执行了 heapify 操作，在此期间旧密钥可能破坏了堆不变性（具有更高的优先级，但在权重更新后可能被放错了位置）并且任何后续的堆化操作都在此之上旧节点可能会使堆处于不一致状态。想法????

Answer 1

问题是您正在更改权重，而不是重新排序队列。在您的示例中，您添加了三个值为 0、1 和 2 的项目。PriorityQueue 在内部使用二进制堆。创建的堆是：

      1
    /   \
   2     3

然后您将 2 节点的值更改为 0，导致此无效堆：

      1
    /   \
   0     3

现在你有一个无效的堆。在二叉最小堆中，每个节点都必须小于或等于其父节点。但在这种情况下，1 是 0 的父级。从现在开始，您对堆进行的任何操作都将产生不可预知的结果。

Java PriorityQueue 不适合更改节点优先级。它没有删除任意元素的方法，也不会让您访问后备存储，因此您不能自己编写。如果你想要改变节点优先级的能力，你必须找到一个支持它的优先级队列实现，或者自己动手。

Java 的 PriorityQueue 显示添加了更高优先级的重复键的意外行为

Java's PriorityQueue showing unexpected behavior for duplicate keys added with higher priority

java

heap

priority-queue

binary-heap