algorithm - 为什么在 heapify 中 siftDown 比 siftUp 好？

Question

要构建最大堆树，我们可以siftDown或 siftUp ，通过向下筛选我们从根开始并将它与它的两个 child 进行比较，然后我们用两个 child 中较大的元素替换它，如果两个 child 都较小则我们停止，否则我们继续向下筛选该元素直到我们达到叶节点(或者当然再次，直到该元素大于它的两个子节点)。

现在我们只需要这样做n/2次，因为叶子的数量是 n/2 ，当我们完成对最后一个(叶子之前)级别上的最后一个元素的堆化时，叶子将满足堆属性 - 所以我们将留下 n/2。堆化的元素。

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

我的问题是:当我们使用 siftDown 时，我们基本上不是在进行两次比较(将元素与其两个子元素进行比较)，而不是在使用 siftUp 时只进行一次比较吗？ ，因为我们只将该元素与其一个父元素进行比较？如果是，那是否意味着我们将复杂性加倍并最终得到与筛选完全相同的复杂性？

Answer 1

实际上，通过重复调用 siftDown 构建堆的复杂度为 O(n) 而通过重复调用 siftUp 构建堆复杂度为 O(nlogn)。

这是因为当您使用siftDown时，每次调用所花费的时间随着节点的深度减少，因为这些节点更靠近叶子.当您使用 siftUp 时，交换次数会随着节点的深度增加，因为如果您处于全深度，您可能必须一直交换到根。随着节点数量随树的深度呈指数增长，使用 siftUp 会给出更昂贵的算法。

此外，如果您正在使用最大堆进行某种排序，其中弹出堆的最大元素然后重新堆化它，使用 siftDown 会更容易做到这一点。您可以在 O(logn) 时间内重新堆化，方法是弹出最大元素，将最后一个元素放在根节点(它是空的，因为您弹出了它)，然后将它一直筛选回到它的位置正确的位置。