删除元素时 PriorityQueue 改变顺序

Question

在不提供自定义比较器的情况下，优先级队列按升序插入元素，但是，在删除特定元素后，顺序会发生变化。

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(1);
pq.add(2);
pq.add(2);
    
pq.remove(2);
for(int x: pq) {
    System.out.println(x);
}

//outputs: 1 10 2, instead of expected: 1 2 10

有什么想法吗？

谢谢。

Answer 1

不要像在 collections/arrays 上那样重复 PriorityQueue<T>；使用 .poll()，而不是：

while(pq.peek()!=null) {
    System.out.println(pq.poll());
}

优先级队列是一种抽象数据类型，通常作为 Binary Heap 数据结构实现，而后者又（通常）用数组实现。 _{还有其他一些方法可以实现二叉堆，但是普通数组是最快、最简单、最好的方法。}

数组如何表示二进制堆的示例，如下所示：

Queue order 未更改，在您的情况下；相反，您只是以错误的方式使用数据结构，仅通过传统的 for-each/迭代方式对其进行迭代，就像在基本数组上进行迭代时一样，而不考虑您的优先级队列支持数组是未按其 i^th 索引排序；相反，它将顶部元素保留在树的顶部（最小堆或最大堆的情况）并且您不能仅通过以传统方式对其进行迭代来获得 .poll() 效果。

Answer 2

这是因为 PriorityQueue 是最小堆的实现（默认在 Java 中），这意味着根元素将始终低于列表中的其他元素。

以你的问题为例：

插入10时，数组中索引1处的元素为10
当你插入 1 时，因为 1 < 10 位置 1 的元素现在是 1 而 10 它移动到索引 2
当你插入2时，因为1 < 2不需要移动元素，2被插入到索引3
当你插入 2 时，2 将小于 10，因为 10 > 2 需要一个移位，2 被插入到 2 并且 10 被写入索引 4

所有插入数组后看起来是这样的，同时查看下面的视频：

array: [NULL, 1, 2, 2, 10]

现在当你删除 2 时，10 需要移位，并且 10 被移回索引 2，并且数组的状态是 [NULL, 1, 10, 2] 这就是你在迭代时看到的输出.另外，检查在 PriorityQueue 中实现的 the following method，当您不提供 Comparator.

时使用

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

删除元素时 PriorityQueue 改变顺序

PriorityQueue changes order when removing an element

java

data-structures

priority-queue