2

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

3 回答 3

3

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

二叉堆只保证每个 子堆（子树）中的根是最小的元素。
堆实际上是一个完整的树（或它的数组表示）。每当您插入违反条件的元素（小于根）时，旧的根就会被筛选掉。这是在堆上递归完成的。

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

于 2012-09-11T12:01:46.210 回答
2

PriorityQueue 是一种树状结构，可确保第一个元素是最小的。其他元素的顺序并不重要，很可能是由于 PQ 如何平衡树。

正如@larsmans 指出的那样，这被称为最小堆顺序

于 2012-09-11T12:01:15.107 回答
2

Java 文档：

An unbounded priority queue based on a priority heap. 
The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. 
A priority queue does not permit null elements. 
A priority queue relying on natural ordering also does not permit insertion of 
non-comparable objects (doing so may result in ClassCastException).

还说：

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

你输出的是toString()方法。输出是由于该方法如何迭代树。与 的顺序相同Iterator。

于 2012-09-11T12:03:21.627 回答