一尘不染

为什么在Java中的PriorityQueue中会发生这种奇怪的顺序?[重复]

algorithm

我阅读了文档以及可以找到的关于PriorityQueue的所有信息,但仍然不明白为什么输出如此奇怪,我的意思是我无法理解添加订单的意义,有人可以解释吗?

PriorityQueue<String> pq = new PriorityQueue<String>();
pq.offer("2"); 
System.out.println("add 2 : " + pq); 
pq.offer("4");
System.out.println("add 4 : " + pq);
System.out.println(pq.peek() + " ");
pq.offer("1");
System.out.println("offer 1 : " + pq);
pq.offer("3");
System.out.println("add 3 : " + pq);
pq.remove("1");
System.out.println("remove 1 : " + pq);

输出:

add 2 : [2]
add 4 : [2, 4]            <- why 4 goes there
offer 1 : [1, 4, 2]       <- why 1 goes first
add 3 : [1, 3, 2, 4]      <- why reorder
remove 1 : [2, 3, 4]      <- again

阅读 478

收藏
2020-07-28

共1个答案

一尘不染

PriorityQueue 仅保证第一个元素最小。

二进制堆仅在每个子HEAB(子树)保证根是最小的元素。
堆实际上是一个完整树(或它的数组表示形式)。每当您插入违反条件的元素(小于根)时,都会过滤掉旧根。这是在堆上递归完成的。

这种部分排序允许快速且相对高速缓存有效(具有数组表示)的数据结构,如果您在每个时间点仅需要min元素,则可以使用该结构。

2020-07-28