爲什麼siftDown比heapify中的siftUp更好？

要構建MAX堆樹，我們可以使用siftDown或siftUp，通過篩選我們從根開始並將其與兩個孩子進行比較，然後用兩個孩子中較大的元素替換它，如果兩個孩子都較小那麼我們停下來，否則我們繼續篩選那個元素直到我們到達一個葉節點（或者當然，直到那個元素大於它的兩個孩子）。爲什麼siftDown比heapify中的siftUp更好？

現在我們只需要做n/2次，因爲樹葉的數量是n/2，當我們在最後一層之前（樹葉之前）完成層上最後一個元素的堆疊時，樹葉將滿足堆屬性。所以我們將留下n/2元素來堆積。

現在，如果我們使用siftUp，我們將從葉子開始，最終我們將需要堆積所有n元素。

我的問題是：當我們使用siftDown，不是我們基本上做兩個比較（元素比較它的兩個孩子），而不是隻有一個比較使用siftUp的時候，因爲我們只該元素比較其父母一方？如果是的話，那不就意味着我們將複雜性加倍，真正結束與篩選一樣的複雜性嗎？

來源

2012-10-23 Roronoa Zoro

我認爲這個問題的答案適用。也許是重複的。 https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity –

實際上，構建一個重複調用siftDown的堆的複雜度爲O(n)，而用siftUp的重複調用構建它的複雜度爲O(nlogn)。

這是因爲，當你使用siftDown，每次調用所花費的時間減少與節點的深度，因爲這些節點接近葉子的事實。當您使用siftUp時，交換次數會隨着節點的深度而增加，因爲如果處於全深度，則可能必須一直交換到根目錄。隨着樹的數量隨着樹的深度呈指數增長，使用siftUp給出了更昂貴的算法。此外，如果您正在使用最大堆進行某種排序，在那裏您彈出堆的最大元素，然後重新對它進行重新組合，使用siftDown可以更容易地完成此操作。你可以在O(logn)時間內通過彈出最大元素，將最後一個元素放在根節點（因爲彈出它而爲空），然後將其一直篩選回到正確的位置，從而重新進行聚合。

來源

2012-10-23 08:09:31 alestanis

如何用SiftDown和複雜度O（n）構建堆？ –

在這裏檢查：http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity – sha1

我可能是錯的，但在我看來，應該區分平均複雜性和最壞情況的複雜性由於在堆中插入元素的平均複雜度爲O（1），因此在我看來'siftUp'的平均複雜度與'siftDown'相同。在我看來，差異是在最壞的情況下：'siftUp'將是O（nlogn），而'siftDown'只會是O（n）。你能確認嗎？ –

爲什麼siftDown比heapify中的siftUp更好？

回答

相關問題