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

Question

看完Why siftDown is better than siftUp in heapify?等问题后我的印象

1. siftDown() 优于 siftUp()
2. siftDown() 总是可以替代 siftUp()，反之亦然

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

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) 次交换，因为你最终必须将 something 放在数组中的第 (n+1) 个位置(即你必须添加一个项)。

应该清楚，您不想在顶部插入，尽管在删除根时必须执行非常相似的操作。

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

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