如果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（）操作，其中有很多不必要的附加比较。