如果siftDown比siftUp更好，爲什麼我們擁有它？

Question

讀書問題，如Why siftDown is better than siftUp in heapify?後，我得到的印象

1. siftDown（）比siftUp（）
2. siftDown（）更可隨時更換siftUp（）和反之亦然

爲什麼是否有大量的堆結構實現有siftUp（）在insert（）上調用？有Wikipedia的article。

Answer 1

將元素向下篩選的BuildHeap方法是將現有數組轉換爲堆的最快速已知方法。它比一次插入一個項目要快，並且比從底部篩選元素要快。

但是，一旦構建了堆並且您正在執行一系列插入操作並刪除數據結構，則在底部插入項目並篩選它們比插入頂部和篩選要快下。

請記住，在n個物品堆中，n/2個物品位於葉級別。這意味着當你插入一個物品時（通過添加它作爲下一個葉​​子），有50％的機會不需要篩選：它已經在適當的位置。有25％的機率屬於下一級別。隨着你在堆中移動，物品篩選到該級別的概率降低50％。

現在，你可能寫你堆代碼做頂部插入的所有時間，但概率工作對你。您插入的項目仍有50％的可能性會在葉級別結束。除非你在頂部插入它會讓你記錄（n）交換到那裏。

所以，如果你在底部插入，並篩選了起來：

50% of the time you make 0 swaps 
25% of the time you make 1 swap 
12.5% of the time you make 2 swaps 
... 

如果插入頂部和篩選下來：

50% of the time you make log(n) swaps 
25% of the time you make log(n)-1 swaps 
12.5% of the time you make log(n)-2 swaps 
... 

試想想它，它比這更糟糕。因爲如果你插入一個物品並且它最終在中間的某個地方着陸，那麼你必須把它移動的物品並篩選它，然後篩選它。這將最終導致整個事情都在堆積如山。最後，插入頂部總是花費你記錄（n）交換，因爲你最終必須在數組中第（n + 1）個位置放置（即你必須添加一個項目）。

應該清楚的是，你不想插入頂部，儘管當你刪除根目錄時你必須做一些非常相似的事情。

當您刪除根目錄時，將堆中的最後一項放入根目錄並篩選。考慮到你是從葉級獲得它的，並且考慮到葉級包含了一半的項目，那麼它有一個很好的機會（比50％好一點），它將最終回到葉級。請注意，這不會始終導致log（n）交換，因爲您沒有插入項目;你只是重新調整堆。

這就是爲什麼在一個寫得很好的二進制堆實現中，刪除根元素比插入一個新項更昂貴。

Answer 2

[編輯這個答案讓人們不必通過評論閱讀]

，似乎迷惑你是建立使用的輸入一組數字從頭樹的方法的事情。

有一種算法首先創建一個隨機樹，然後從下往上工作並篩選出可找到的任何東西。該算法比將每個元素相互插入並篩選出來要快。

但是，插入方法本身只插入一個元素，而不是它們的整個列表。所以建立樹和插入一個元素是有區別的。

當你插入一個元素並且使用相同的算法時，你會做很多無意義的比較，因爲你已經知道大部分樹已經在工作。在每次迭代中（從下到上），總是隻有一個可能改變的子樹（帶有新輸入的子樹）。所以這是唯一真正需要考慮的問題。

由於樹的其餘部分沒有隨機化，這也意味着在推新輸入之後，不需要篩選。它下面的所有東西都已經準備就緒。所以最後，即使你使用插入一個單一元素的算法，你所做的只是一個簡單的siftUp（）操作，其中有很多不必要的附加比較。