为什么这个奇怪的顺序发生在java的PriorityQueue中？

我阅读文档和我能找到的关于PriorityQueue的一切，但仍然不明白为什么输出是如此奇怪我的意思是我不能得到一个添加顺序的点，任何人都可以解释？

PriorityQueue pq = new PriorityQueue(); 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 

Answer 1

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

二进制堆仅在每个子heab（子树）中保证根是最小元素。
堆实际上是一个完整的树（或它的数组表示）。 每当您插入违反条件的元素（小于根）时，旧的根被向下筛选。 这是通过堆递归完成的。

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

Answer 2

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

正如@larsmans指出的那样，这被称为min heap order

Answer 3

Java doc：

 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相同的顺序。