为什么在堆化过程中，siftDown比siftUp更好？

Question

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

现在我们只需要这样做n/2次，因为叶节点的数量是n/2，并且当我们完成最后一个元素的堆化时，在最后一层（即叶节点之前的那一层）之前，所有叶节点都将满足堆属性 - 因此我们将剩下n/2个元素需要进行堆化。

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

我的问题是：当我们使用siftDown时，我们不是基本上要做两次比较（将元素与其两个子节点进行比较），而使用siftUp时只需进行一次比较（将该元素与其一个父节点进行比较）吗？如果是的话，这不意味着我们正在将复杂度加倍，并最终以与sift down完全相同的复杂度结束吗？

- Roronoa Zoro

---

我认为这个问题的答案适用。可能是重复的。https://dev59.com/dGkw5IYBdhLWcg3wn8CO - Jeremy West

Answer 1

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

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

此外，如果您正在使用最大堆来进行某种排序(弹出堆的最大元素然后重新堆化)，那么使用 siftDown 更容易实现。通过弹出最大元素，将最后一个元素放在根节点（因为已经弹出），然后将其向下移动到正确位置，您可以在 O(logn) 的时间内重新堆化。

- alestanis

---

如何使用SiftDown构建具有O(n)复杂度的堆？ - Munish Goyal

请查看此处：https://dev59.com/dGkw5IYBdhLWcg3wn8CO - sha1

我可能错了，但我认为人们应该区分平均复杂度和最坏情况下的复杂度。由于在堆中插入元素的平均复杂度为O（1），因此我认为siftUp的平均复杂度与siftDown相同。我认为差异在于最坏情况下：siftUp将是O（nlogn），而siftDown仅为O（n）。你能确认一下吗？ - Vic Seedoubleyew

@VicSeedoubleyew，二叉堆插入的平均复杂度为O(logn)，因为通常情况下，元素将被添加到树的末尾O(1)，然后通过siftUp移动到正确的位置O(logn)。正如您所建议的，siftUp的平均复杂度将与siftDown相同。事实证明，无论是Up还是Down，sift的最坏情况复杂度都将是O(logn)。唯一存在差异的地方是特定于heapifying的原因，正如@alestanis所述。 - EnigmaticBacon