如果 siftDown 比 siftUp 更好，为什么我们要它？

Question

看了Why siftDown is better than siftUp in heapify?等问题后，我有了印象

为什么很多堆结构实现都有在insert()上调用的siftUp()？维基百科的 article 有。

Answer 1

[编辑了这个答案，这样人们就不必通读评论了]

似乎让您感到困惑的是使用一定数量的输入从头开始构建树的方法。

有这样一种算法，它首先创建一个随机树，然后从下到上工作并筛选它能找到的任何东西。该算法比将每个元素依次插入并筛选要快。

但是，insert 方法本身只插入一个元素，而不是整个列表。所以建树和插入一个元素是有区别的

当您插入一个元素并使用相同的算法时，您会进行大量毫无意义的比较，因为您已经知道树的大部分已经在工作。在每次迭代中（从下到上），始终只有一个子树可能会发生变化（具有新输入的子树）。所以这是唯一真正需要关注的。

并且由于树的其余部分不是随机的，这也意味着在将新输入向上推后，您不需要向下筛选。它下面的所有内容都已按顺序排列。

所以最后，即使您确实使用插入单个元素的算法，您所做的也只是一个简单的 siftUp() 操作，带有许多不必要的额外比较。

Answer 2

筛选元素的 BuildHeap 方法是已知最快的将现有数组转换为堆的方法。比一次插入一项要快，也比从下往上筛选元素要快。

但是，一旦构建了一个堆，并且您在数据结构上进行了一系列插入和删除操作，那么在底部插入项并筛选它们比在顶部插入和筛选要快筛选。

请记住，在 n 个项目的堆中，n/2 个项目处于叶级。这意味着当您插入一个项目（通过将其添加为下一个叶子）时，有 50% 的机会它不必筛选：它已经在正确的位置。它有 25% 的几率属于下一层。当您在堆中向上移动时，项目筛选到该级别的概率降低 50%。

现在，您可以编写堆代码来始终在顶部进行插入，但概率对您不利。您插入的项目仍有 50% 的机会最终出现在叶级别。除非你在顶部插入它会带你 log(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
...

想想看，比那更糟。因为如果你插入一个项目并且它最终落在中间的某个地方，那么你必须拿走它移动的项目并向下筛选 it。这将最终导致整个堆中的东西向下移动。最后，在顶部插入总是花费你 log(n) 次交换，因为你最终必须将 something 放在数组中的第 (n+1) 个位置（即你有添加项目）。

很明显您不想在顶部插入，尽管在删除根时您必须做一些非常相似的事情。

当你移除根时，你取出堆中的最后一项，将它放在根位置，然后向下筛选。考虑到您是从叶级别获取它的，并且考虑到叶级别包含一半的项目，它很有可能（略高于 50%）最终回到叶级别。请注意，这不会 always 导致 log(n) 交换，因为您没有插入项目；你只是在重新调整堆。

这就是为什么，顺便说一句，在编写良好的二叉堆实现中，删除根元素比插入新元素的成本更高。

If siftDown is better than siftUp why do we have it?