为什么这个奇怪的顺序发生在PriorityQueue中使用Java？ [英] Why is this strange order happens in PriorityQueue in java?

问题描述

我读的文档和所有我能找到的PriorityQueue，但还是不明白为什么输出是这么奇怪我的意思是，我不能拿到一分加料顺序的，任何人都可以解释一下吗？

 的PriorityQueue＆LT;字符串＆GT; PQ =新的PriorityQueue＆LT;字符串＆GT;（）;
pq.offer（2）;
的System.out.println（加2+ PQ）;
pq.offer（4）;
的System.out.println（加4+ PQ）;
的System.out.println（pq.peek（）+）;
pq.offer（1）;
的System.out.println（要约1：+ PQ）;
pq.offer（3）;
的System.out.println（加3+ PQ）;
pq.remove（1）;
的System.out.println（删除1：+ PQ）;
 

输出：

 加2：2]
加4：2，4]＆LT;  - 为什么4去那里
优惠1：1，4，2]＆LT;  - 为什么1先行
添加3：[1，3,2，4]其中;  - 为什么重新排序
删除1：2，3，4]＆LT;  - 再次
 

解决方案

的PriorityQueue 只保证第一个元素是最小的。

一个二元堆在每个子HEAB（子树），既保证了根的最小元素。
堆实际上是一个完整的树（或重新它presentation数组）。当你插入违反条件（越小则根）的元素，老根被筛下来。这是在堆完成递归。

这部分排序允许快速和相对高速缓存效率（用数组重新presentation），可以使用，如果你只需要最小的元素在每个点的时间数据结构。

I read documentation and everything i could find about PriorityQueue, but still don't get why output is so strange I mean I can't get a point of adding order, can anyone explain?

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);

Output:

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 only guarantees that the first element is the smallest.

A binary heap only guarantees in each sub-heab (sub-tree) the root is the smallest element.
The heap is actually a complete-tree (or an array representation of it). Whenever you insert an element that violates the condition (is smaller then the root), the old root is sifted down. this is done recursively over the heap.

This partial ordering allows fast and relatively cache-efficient (with array representation) data structure that can be used if you only need the min element at each point at time.

这篇关于为什么这个奇怪的顺序发生在PriorityQueue中使用Java？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！