为什么在heapify中siftDown优于siftUp？

要构建MAX堆树，我们可以选择siftDown或siftUp，通过从根开始向下筛选并将其与两个孩子进行比较，然后将其替换为两个孩子中较大的元素，如果两个孩子都较小，则我们停止，否则，我们将继续向下过滤该元素，直到到达叶节点（或者当然，直到该元素大于其两个子元素为止）。

现在我们只需要这样做n/2一次，因为叶子的数量为n/2，并且当我们完成对最后一个元素之前（叶子之前）的层上的最后一个元素进行堆放时，叶子将满足heap属性-

因此我们将剩下n/2要堆化的元素。

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

我的问题是：当使用时siftDown，我们基本上不是在进行两次比较（将元素与其两个子元素进行比较），而不是使用时仅进行一次比较siftUp，因为我们仅将该元素与其一个父元素进行比较？如果是，那是否就意味着我们将复杂度提高了一倍，并最终真正获得了与筛选相同的复杂度？

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

这是由于这样的事实，当您使用siftDown时，每次调用所花费的时间随着节点的深度而

，因为这些节点更靠近叶子。当使用时siftUp，交换的随节点的深度而

，因为如果您处于最大深度，则可能必须一直交换到根。随着节点数量随树的深度呈指数增长，使用siftUp给出了更昂贵的算法。

此外，如果您正在使用Max-

heap进行某种排序，请在其中弹出堆的max元素，然后对其进行重新堆砌，使用会更容易实现siftDown。您可以O(logn)通过弹出max元素，将最后一个元素放在根节点（由于弹出而为空）中，然后重新筛选到正确位置，从而及时重新堆砌。