16

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

现在我们只需要这样做n/2，因为叶子的数量是n/2，并且当我们在最后一层（叶子之前）上完成对最后一个元素的堆化时，叶子将满足堆属性 - 所以我们将剩下n/2要堆积的元素。

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

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

4

1 回答 1

30

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

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

此外，如果您使用 Max-heap 进行某种排序，您会弹出堆的最大元素，然后重新堆化它，使用siftDown. 您可以O(logn)通过弹出最大元素，将最后一个元素放在根节点（因为您弹出它是空的）然后将它一直筛选到正确的位置来及时重新堆放。

于 2012-10-23T08:09:31.683 回答