要构建最大堆树，我们可以siftDown或siftUp，通过从根开始筛选，并将其与两个子元素进行比较，然后将其替换为两个子元素中较大的元素，如果两个子元素都较小，则停止，否则继续向下筛选该元素，直到到达叶节点（或者再次筛选，直到那个元素比它的两个子元素都大）。
现在我们只需要执行n/2次，因为叶子的数量是n/2，当我们在最后一个元素之前（叶子之前）的级别上完成heapify最后一个元素时，叶子将满足heap属性，因此我们将留下n/2个元素来进行heapify。
现在如果我们使用siftUp，我们将从叶子开始，最终我们将需要修复所有n元素。
我的问题是：当我们使用siftDown时，我们基本上不是在做两个比较（将元素与它的两个子元素进行比较），而不是在使用siftUp时只进行一个比较，因为我们只将该元素与它的一个父元素进行比较？如果是的话，这难道不意味着我们把复杂性加倍了吗？
最佳答案
实际上，构建一个重复调用“cc>”的堆具有复杂的siftDown，而用重复调用的方式构建O(n)具有复杂的siftUp。
这是因为当您使用O(nlogn)时，每个调用所花费的时间随着节点的深度而减少，因为这些节点更靠近叶子。当您使用siftDown时，交换的数量会随着节点的深度而增加，因为如果您处于完全深度，则可能必须一直交换到根节点。随着节点数随着树的深度呈指数增长，使用siftUp提供了一种更昂贵的算法。
此外，如果使用max堆进行某种排序，在其中弹出堆的max元素，然后重新获取它，则使用siftUp更容易做到这一点。您可以在siftDown时间内通过弹出max元素，将最后一个元素放在根节点（因为您弹出了它，所以根节点是空的）上，然后一直向下筛选到正确的位置来重新获取。
关于algorithm - 为什么在heapify中siftDown比siftUp更好？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13025163/