为什么siftDown比siftUp在heapify更好？(Why siftDown is bett

要构建最大堆树，我们可以siftDown或siftUp ，通过筛选下来，我们从根开始，并将它与它的两个孩子，那么我们有两个孩子的更大的元素替换它，如果这两个孩子是小然后我们停止，否则我们继续筛选该元素，直到我们（或课程的再次，直到该元素是它的两个孩子大）到达叶节点。

现在，我们只需要做到这一点n/2次，因为叶子的数量为n/2 ，和叶子会满足，当我们完成heapifying上水平的最后一个元素之前的最后一个堆性质（前叶） -因此，我们将留下n/2的元素heapify。

现在，如果我们使用siftUp ，我们将与叶开始，最终我们需要heapify所有n元素。

我的问题是：当我们使用siftDown ，不是我们基本上做两个比较（对比元素，它的两个孩子），而不是只有一个比较使用时siftUp ，因为我们只该元素比较其父母一方？ 如果是的话，那不就意味着我们正在加倍的复杂性和真正结束了作为筛选下来完全相同的复杂性？

Answer 1:

事实上，建立一个堆有多次呼吁siftDown具有的复杂性O(n)而与多次呼吁建立它siftUp具有的复杂性O(nlogn)

这是因为，当你用事实siftDown ，每次调用所花费的时间与节点的深度减小 ，因为这些节点接近叶子。 当您使用siftUp ，掉期的数量与节点的深度增加 ，因为如果你在全深度，你可能不得不一路换到根。 随着节点的数量与树的深度呈指数增长，使用siftUp给出了一个更昂贵的算法。

此外，如果您使用的是最大堆在那里你弹出堆的最大元素做一些排序，然后reheapify它，它更容易通过这样做siftDown 。 您可以在reheapify O(logn)通过弹出的最大元素时，把最后一个元素根节点（因为你弹出它这是空的），然后筛选下来一路回到它的正确位置。

文章来源: Why siftDown is better than siftUp in heapify?