为什么siftDown比heapify中的siftUp好？

Question

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

现在我们只需要做那些n/2时间,因为叶子的数量是n/2,当我们完成堆积最后一个元素(在叶子之前)之前的水平上时叶子将满足堆属性 - 所以我们将留下n/2要堆积的元素.

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

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

Answer 1

实际上,使用重复调用构建堆具有siftDown复杂性,O(n)而使用重复调用来构建堆具有siftUp复杂性O(nlogn).

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

此外,如果您使用Max-heap进行某种排序,其中弹出堆的max元素然后重新定义它,则使用它更容易siftDown.您可以O(logn)通过弹出max元素及时将最后一个元素放在根节点(由于弹出它而为空)然后将其一直向下筛回到正确的位置来及时重新定义.