爲什麼在Java中的PriorityQueue中發生這種奇怪的順序？

我閱讀了文檔和我能找到的有關PriorityQueue的所有內容，但仍然不明白爲什麼輸出很奇怪我的意思是我無法獲得添加順序的一個要點，任何人都可以解釋嗎？
爲什麼在Java中的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

來源

2012-09-11 Nikolas Papirniy

元素使用[堆序]（https://en.wikipedia.org/wiki/Heap_%28data_structure%29）。 –

需要考慮的是'PriorityQueue'實現'toString'的方式是這樣的，它命令String中的值。由於'toString'似乎是在'AbstractCollection'中實現的，所以我建議它可能不會。嘗試使用'poll'以正確的順序獲取元素。 –

@JohnB從AbstractCollection中獲得：「字符串表示形式由集合元素的列表組成，其順序由括號（」[]「）括起來。如果PriorityQueue不覆蓋該方法本身，那麼應該保證它是有序的（儘管不一定如你所期望的那樣）。 –

PriorityQueue只保證第一個元素是最小的。

A binary heap只保證在每個子heab（子樹）中根是最小的元素。
堆實際上是一個完整的樹（或它的數組表示）。無論何時插入違反條件的元素（小於根），都會篩選舊的根。這是通過堆遞歸地完成的。

此部分排序允許快速且相對緩存高效（具有數組表示形式）的數據結構，如果您在每個時間點只需要min元素，就可以使用這種結構。

來源

2012-09-11 12:01:46 amit

的PriorityQueue是樹狀結構，其確保第一元件是最小的。其他元素的順序並不重要，可能是由於PQ如何平衡樹。

作爲@larsmans所指出的，這被稱爲最小堆順序

來源

2012-09-11 12:01:15

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-11 12:03:21 ssedano

爲什麼在Java中的PriorityQueue中發生這種奇怪的順序？

回答

相關問題