最小堆是如何創建的？

在代碼中給出一串字符串，我們返回流中k個最長的字符串。我的問題是比較器是如何工作的？我知道我們正在使用一個匿名函數來重寫比較方法來比較兩個字符串的長度，但這個比較如何創建一個最小堆？最小堆是如何創建的？

public static List<String> topK(int k, Iterator<String> iter) { 
PriorityQueue<String> minHeap = new PriorityQueue<>(k, new Comparator<String>() { 
    public int compare(String s1, String s2) { 
    return Integer.compare(s1.length(), s2.length()); 
    } 
}); 
while (iter.hasNext()) { 
    minHeap.add(iter.next()); 
    if (minHeap.size() > k) { 
    // Remove the shortest string. Note that the comparison function above 
    // will order the strings by length. 
    minHeap.poll(); 
    } 
} 
return new ArrayList<>(minHeap); 
}

來源

2017-10-07 Matt

您是否閱讀過PriorityQueue的javadoc？ https://docs.oracle.com/javase/9/docs/api/java/util/PriorityQueue.html –

很難理解你在問什麼。「這個比較如何創造一個最小的堆」這個問題是不合情理的。比較*不會創建最小堆。 'PriorityQueue'代碼通過使用您提供的比較器來訂購堆中的項目來創建最小堆。請澄清你的問題。 –

從Javadoc of PriorityQueue：

這個隊列的頭是相對於指定的排序的最小元素。

而且PriorityQueue.poll()：

獲取並移除此隊列的頭，或者返回null，如果此隊列爲空。

比較器通過增加長度來排序元素，所以隊列的頭部是長度最小的元素。因此，當您調用poll()時，最短的字符串將從隊列中移除。

如果彈出以便只保留隊列中最多的k項，那麼這些將是迄今爲止從迭代器獲取的最長項目k。一旦迭代器耗盡，那些將是（最多）k最長的項目。

來源

2017-10-07 22:03:22

試圖在容易句話來概括

二進制堆是二進制隊列後面一種特殊類型的樹的數據結構。在堆中，每個節點及其子節點遵循一些常見模式。例如，在最小堆中，所有子節點都必須大於父節點。因此，根節點保持最小的數量。

在堆中，當堆中有任何改變（插入，刪除，更新）時，堆以某種方式進行重構，從而保持共同原則（例如，在上述情況下，父始終保持始終小於其子女）。所以當在堆上完成一些操作時，會調用heapify操作。對於最小堆來說，最小堆積將被稱爲維持原則。因此，在最小heapify操作中，將父節點與子節點進行遞歸比較，以檢查哪個節點的值較低，如果孩子的值較低，則將與父節點交換。

現在在你的情況下，你只是實現heapify操作的比較方法。所以對於最大堆，你只需要做相反的事情（設置更高的值作爲父母）。此外，您可以通過滿足您自己的需求來實現自定義比較方法。

要了解更多詳細信息，您可以使用二進制堆進行搜索，並且您可以找到很多優秀的資源。

來源

2017-10-07 22:02:34 stinepike

最小堆是如何創建的？

回答

相關問題