優先級隊列中的排序與未排序數據爲什麼自動排序和排序等待？

我知道最小堆是類使用的結構，因爲它的效率很高。在我看來，當將未排序的數據提供給PQ時，會將其分類爲堆。優先級隊列中的排序與未排序數據爲什麼自動排序和排序等待？

但是當按照compareTo方法提供元素時，它會在PQ上執行第一個操作後等待將其排序到堆中。

你知道這是爲什麼嗎？我不明白爲什麼它不像無序數據那樣自動排序。

我附上了一個程序，我認爲證明了我的問題。

輸出：

未排序的數據：

[A，B，d，C，L，F，E，J]

甲

[B，C， d，J，L，F，E]

[1，2，4，3，12，6，5，10]

[2，3，4，10，12，6，5]

排序的數據：

[A，B，C，d，E，F，G ，H]

甲

[B，d，C，H，E，F，G]

[1，2，3，4，5，6，7，8]

[2,4，3,8，5，6，7]

import java.util.PriorityQueue; 

public class Queue2 
{ 
    public static void main(String[] args) 
    { 
     PriorityQueue<String> pQueue = new PriorityQueue<String>(); 

     pQueue.add("A"); 
     pQueue.add("C"); 
     pQueue.add("F"); 
     pQueue.add("B"); 
     pQueue.add("L"); 
     pQueue.add("D"); 
     pQueue.add("E"); 
     pQueue.add("J"); 
     System.out.println(pQueue); 
     System.out.println(pQueue.remove()); 
     System.out.println(pQueue); 

     System.out.println(); 

     PriorityQueue<Integer> pQueue2 = new PriorityQueue<Integer>(); 

     pQueue2.add(1); 
     pQueue2.add(3); 
     pQueue2.add(6); 
     pQueue2.add(2); 
     pQueue2.add(12); 
     pQueue2.add(4); 
     pQueue2.add(5); 
     pQueue2.add(10); 
     System.out.println(pQueue2); 
     System.out.println(pQueue2.remove()); 
     System.out.println(pQueue2); 

     System.out.println(); 

     PriorityQueue<String> pQueue3 = new PriorityQueue<String>(); 

     pQueue3.add("A"); 
     pQueue3.add("B"); 
     pQueue3.add("C"); 
     pQueue3.add("D"); 
     pQueue3.add("E"); 
     pQueue3.add("F"); 
     pQueue3.add("G"); 
     pQueue3.add("H"); 
     System.out.println(pQueue3); 
     System.out.println(pQueue3.remove()); 
     System.out.println(pQueue3); 

     System.out.println(); 

     PriorityQueue<Integer> pQueue4 = new PriorityQueue<Integer>(); 

     pQueue4.add(1); 
     pQueue4.add(2); 
     pQueue4.add(3); 
     pQueue4.add(4); 
     pQueue4.add(5); 
     pQueue4.add(6); 
     pQueue4.add(7); 
     pQueue4.add(8); 
     System.out.println(pQueue4); 
     System.out.println(pQueue4.remove()); 
     System.out.println(pQueue4); 

    } 
}

來源

2013-05-28 user2428874

所以你知道有隊列下方的（二進制）堆，是嗎？堆應該堅持兩個properties：

的形狀屬性：樹是完全二叉樹;也就是說，除了可能最後一個（最深）的樹以外，樹的所有級別都被完全填充，並且如果樹的最後一級未完成，則該級別的節點將從左到右填充。
heap屬性：根據爲數據結構定義的比較謂詞，每個節點大於或等於其每個子節點。

那麼如何插入元素？做一個BFS直到你找到一個空白點（把該元素放在那個點上），或者找到另一個比當前元素大的元素（用新元素替換那個元素並繼續使用更大的元素）。

讓我們來看看你的兩個例子。我將逐級寫入樹，因此[A][BC][D---]表示以A作爲根的樹，B和CA和D的子節點B的子節點。

我們來看第一個例子：[A, C, F, B, L, D, E, J]。這是堆是如何增長的：

[A] 
[A][C-] 
[A][CF] 
[A][BF][C---] 
[A][BF][CL--] 
[A][BD][CLF-] 
[A][BD][CLFE] 
[A][BD][CLFE][J-------]

現在看看你的排序例如：[A, B, C, D, E, F, G, H]。這是如何堆成長：

[A] 
[A][B-] 
[A][BC] 
[A][BC][D---] 
[A][BC][DE--] 
[A][BC][DEF-] 
[A][BC][DEFG] 
[A][BC][DEFG][H-------]

所以確實，底層數組包含排序順序的所有元素。

那麼，爲什麼這個順序在第一個元素被刪除時失真？爲了滿足堆的兩個屬性，空點重複填充該點的最小子。

讓我們消除A（我標誌着由*空點）後，看看最後一個例子：

[*][BC][DEFG][H-------] 
[B][*C][DEFG][H-------] 
[B][DC][*EFG][H-------] 
[B][DC][HEFG]

這也相當於你給輸出。

來源

2013-05-28 14:54:24

所以我認爲你說的是有序的信息符合形狀和堆屬性，因此是一個min二進制堆，不需要改變。只有當物品被移除時纔會更改。而無序數據需要在堆被更改之前排入堆中。因此，我的問題將是一個糟糕的問題，因爲排序後的數據堆積如山。 – user2428874

@ user2428874好吧，我不認爲這是一個壞問題，但其餘的就是這樣。你打印的是底層數組，它確實代表了二進制最小堆。 –

感謝您的幫助。我覺得有點傻，但你的解釋確實有幫助。我無法提前建立連接。再次感謝！ – user2428874

從PriorityQueue

這個隊列的頭中的文檔是相對於指定的排序的最小元素。如果多個元素的最小值相關聯，則頭是其中一個元素 - 關係被任意破壞。隊列檢索操作輪詢，刪除，查看和元素訪問隊列頭部的元素。

而且

此類及其迭代器實現Collection和Iterator接口的所有可選方法。 方法iterator（）中提供的Iterator不保證以任何特定順序遍歷優先級隊列的元素。如果您需要有序遍歷，請考慮使用Arrays.sort（pq.toArray（））。

這就是爲什麼當你打印隊列（用的System.out）在內部使用和迭代器因此沒有有序輸出的guarenty ......但如果你使用poll()多次，你一定會看到的對象返回在這兩種情況下有序方式

來源

2013-05-28 14:58:28

優先級隊列中的排序與未排序數據爲什麼自動排序和排序等待？

回答

相關問題