时间戳

首页 > 解决方案 > 删除元素时 PriorityQueue 更改顺序

java - 删除元素时 PriorityQueue 更改顺序

问题描述

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

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

有任何想法吗？

谢谢。

标签： javadata-structurespriority-queue

解决方案

不要PriorityQueue<T>像在集合/数组上那样迭代你的；使用.poll(), 代替：

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

优先级队列是一种抽象数据类型，通常实现为二进制堆数据结构，而二进制堆数据结构又（通常）用数组实现。 实现二进制堆还有其他一些方法，但普通数组是最快、最简单、最好的方法。

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

在此处输入图像描述

就您而言，队列顺序没有改变；相反，您只是以错误的方式使用数据结构，仅以传统的for-each/iterative 方式对其进行迭代，就像您在基本数组上进行迭代时一样，不考虑您的 Priority Queue 后备数组未按其 i 排序指数；相反，它维护树顶部的顶部元素（Min Heap 或 Max Heap 情况），您不能仅.poll()通过以传统方式对其进行迭代来获得效果。

推荐阅读