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

  • Z时代
  • 2024-01-10
  • 分类：问答

我阅读了文档以及可以找到的关于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

回答：

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

甲 二进制堆仅在每个子HEAB（子树）保证根是最小的元素。

堆实际上是一个完整树（或它的数组表示形式）。每当您插入违反条件的元素（小于根）时，都会过滤掉旧根。这是在堆上递归完成的。

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

以上是 为什么在Java中的PriorityQueue中会发生这种奇怪的顺序？[重复] 的全部内容， 来源链接： utcz.com/qa/411579.html

回到顶部