java - 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());
}

优先级队列是一种抽象数据类型，通常实现为 Binary Heap数据结构，反过来，它(通常)是用数组实现的。
还有一些其他的方法可以实现二叉堆，但是一个普通的数组，是最快、最简单和最好的方法。
数组如何表示二叉堆的示例如下所示:

在您的情况下，队列顺序没有改变；相反，您只是在以错误的方式使用数据结构，只是在传统的 for-each 中对其进行迭代。/iterative 方式，当您在基本数组上进行迭代时，不考虑您的 Priority Queue 后备数组未按其第 i 个索引进行排序；相反，它维护树顶部的顶部元素(Min Heap 或 Max Heap 情况)，你不能只得到 .poll()通过以传统方式对其进行迭代来产生效果。