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

Question

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

Answer 1

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
...

仔细想想，比这更糟糕。因为如果你要插入一个项目，它结束了在中间的某处登陆，你就必须把它移动的项目，并筛选它下来。这最终会在整个堆中向下移动。最后，在顶部插入总是花费你 log(n) 次交换，因为你最终必须在数组中的第 (n+1) 个位置放置一些东西（即你必须添加一个项目）。

应该清楚的是，您不想在顶部插入，尽管在删除根时您必须做一些非常相似的事情。

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

顺便说一下，这就是为什么在一个编写良好的二进制堆实现中，删除根元素比插入一个新项目更昂贵的原因。