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

不要PriorityQueue<T>像对集合/数组那样进行迭代；使用.poll(), 代替：

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

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

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

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