构建堆的时间复杂度是多少？

Question

有人能帮我解释一下堆的复杂性吗？

向堆中插入一个项是O(log n)，并且插入重复n/2次（剩余的是leaves，不能违反heap属性）。所以，我认为，这意味着复杂性应该是O(n log n)。

换句话说，对于我们“heapify”的每一项，到目前为止，它可能需要为堆的每一级（即log n级）过滤一次。

我错过了什么？

Answer 1

你的分析是正确的。然而，它并不紧。

解释为什么构建堆是一个线性操作并不是一件容易的事，您最好阅读一下。

对该算法进行了大量的分析。

---

其主要思想是，在build_heap算法中，并非所有元素的实际heapify成本都是O(log n)。

当调用heapify时，运行时间取决于进程终止之前元素在树中向下移动的距离。换句话说，它取决于堆中元素的高度。在最坏的情况下，元素可能会一直下降到叶级。

让我们逐级计算所做的工作。

在最底层，有2^(h)个节点，但我们不调用其中任何一个节点上的heapify，因此功为0。在下一个级别有2^(h − 1)个节点，每个节点可能向下移动1个级别。在底部的第三层，有2^(h − 2)个节点，每个节点可能向下移动两层。

正如您所看到的，并不是所有的heapify操作都是O(log n)，这就是您获得O(n)的原因。

Answer 2

直觉上：

"The complexity should be O(nLog n)... for each item we "heapify", it has the potential to have to filter down once for each level for the heap so far (which is log n levels)."

不完全是。你的逻辑并没有产生一个严格的界限——它高估了每个heapify的复杂性。如果自下而上构建，插入（heapify）可以比O(log(n))小得多。流程如下：

（步骤1）第一个n/2元素位于堆的最下面一行。h=0，所以不需要heapify。

（步骤2）下一个{}元素从底部向上排列在第1行。h=1，heapify过滤器一级向下。

（步骤i）下一个n/2i元素从底部向上排列成i。h=i，heapify过滤器i级别降低。

（步骤log（n））最后一个n/2log2(n) = 1元素从底部向上排列成log(n)。h=log(n)，heapify过滤器log(n)级别降低。

注意：第一步之后，1/2元素的(n/2)已经在堆中，我们甚至不需要调用heapify一次。另外，请注意，只有一个元素，根元素，实际上产生了完整的log(n)复杂性。

---

理论上：

构建大小为n的堆的总步骤N可以用数学方法写出。

在高度i处，我们已经（在上面）展示了需要调用heapify的n/2i+1元素，并且我们知道高度i处的heapify是O(i)。这就提供了：

最后求和的方法是取已知几何级数方程两边的导数：

最后，将x = 1/2插入到上述方程中，得到2。将其插入到第一个方程中可以得到：

因此，步骤总数的大小是O(n)

Answer 3

我认为这个话题中隐藏着几个问题：

• 如何实现buildHeap以便它在O（n）时间内运行？
• 如何证明正确实现时buildHeap在O（n）时间内运行？
• 为什么相同的逻辑不能使堆排序在O（n）时间内运行，而不是在O（n logn）时间内运行？

如何实现buildHeap以便它在O（n）时间内运行？

通常，这些问题的答案集中在siftUp和siftDown之间的区别上。在siftUp和siftDown之间做出正确的选择对于获得buildHeap的O（n）性能至关重要，但无助于理解buildHeap和heapSort之间的区别。实际上，正确实现buildHeap和heapSort只会使用siftDown。siftUp操作只需要在现有堆中执行插入，因此它将用于使用二进制堆（例如）实现优先级队列。

我写这篇文章是为了描述最大堆是如何工作的。这是通常用于堆排序或优先级队列的堆类型，较高的值表示较高的优先级。最小堆也很有用；例如，当检索具有升序整数键或字母顺序字符串的项时。原理完全相同；只需切换排序顺序。

堆属性指定二进制堆中的每个节点必须至少与其两个子节点一样大。特别是，这意味着堆中最大的项位于根目录。向下筛选和向上筛选本质上是相同的反向操作：移动有问题的节点，直到它满足堆属性：

• siftDown用最大的子节点交换太小的节点（从而向下移动），直到它至少与下面的两个节点一样大。
• siftUp将太大的节点与其父节点交换（从而将其向上移动），直到它不大于其上的节点。

siftDown和siftUp所需的操作数与节点可能要移动的距离成正比。对于siftDown，它是到树底部的距离，因此siftDown对于树顶部的节点是昂贵的。对于siftUp，工作与到树顶部的距离成正比，因此siftUp对于树底部的节点来说是昂贵的。尽管这两个操作都O（log n）在最坏的情况下，在堆中，只有一个节点位于顶层，而一半节点位于底层。因此，如果我们必须对每个节点应用一个操作，我们宁愿siftDown而不是siftUp，这并不奇怪。

函数buildHeap接受一个未排序项的数组并移动它们，直到它们都满足heap属性，从而生成一个有效的堆。有两种方法可以使用我们描述的siftUp和siftDown操作。

1. 从堆的顶部（数组的开头）开始，对每个项调用siftUp。在每个步骤中，先前筛选的项（数组中当前项之前的项）形成一个有效堆，然后向上筛选下一个项，将其放入堆中的有效位置。在筛选每个节点之后，所有项都满足heap属性。

2. 或者，朝相反的方向走：从数组的末尾开始向后移动到前面。在每次迭代中，您都会向下筛选一个项，直到它位于正确的位置。

哪个实现对buildHeap更有效？

这两个解决方案都将产生一个有效堆。不出所料，效率更高的是使用siftDown的第二个操作。

让h=log n表示堆的高度。siftDown方法所需的工作量由

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

总和中的每一项都有最大距离给定高度的节点必须移动（底层为零，根部为h）乘以该高度的节点数。相反，在每个节点上调用siftUp的总和是

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

应该清楚的是，第二个总和更大。第一项仅为hn/2=1/2n logn，因此该方法最多具有复杂度O（n logn）。

我们如何证明siftDown方法的和确实是O（n）？

一种方法（还有其他的分析方法）是将有限和转化为无穷级数，然后使用泰勒级数。我们可以忽略第一项，它是零：

如果您不确定为什么每个步骤都有效，请使用以下文字说明该过程的理由：

• 这些项都是正的，所以有限和必须小于无限和。
• 该级数等于在x=1/2下计算的幂级数。
• 这个幂级数等于泰勒级数的导数（一个常数倍），对于f（x）=1/（1-x）。
• x=1/2在泰勒级数的收敛区间内。
• 因此，我们可以用1/（1-x）来代替Taylor级数，并对其进行微分和求值，以求得无穷级数的值。

由于无穷和恰好是n，我们得出结论，有限和不大于，因此是O（n）。

为什么堆排序需要O（n logn）时间？

如果可以在线性时间内运行buildHeap，为什么堆排序需要O（n logn）时间？堆排序包括两个阶段。首先，我们调用数组上的buildHeap，如果以最佳方式实现，则需要O（n）时间。下一步是重复删除堆中最大的项，并将其放在数组的末尾。因为我们从堆中删除一个项，所以在堆的末尾总是有一个可以存储该项的开放点。因此，heap sort通过连续删除下一个最大的项并将其放入从最后一个位置开始并朝前移动的数组中来实现排序顺序。堆排序中占主导地位的是最后一部分的复杂性。循环看起来如下：

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

显然，循环运行O（n）次（n-1准确地说，最后一项已经就位）。堆deleteMax的复杂性是O（log n）。它通常是通过删除根（堆中剩余的最大项）并将其替换为堆中的最后一项（叶）来实现的，因此也是最小项之一。这个新根几乎肯定会违反heap属性，因此必须调用siftDown，直到将其移回可接受的位置。这还可以将下一个最大的项移到根上。注意，与buildHeap相反，对于我们从树的底部调用siftDown的大多数节点，我们现在在每次迭代时都从树的顶部调用siftDown！尽管树正在收缩，但它收缩的速度不够快：树的高度保持不变，直到删除了前半个节点（当完全清除底层时）。接下来的四分之一，高度是h-1。所以第二阶段的全部工作是

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

注意开关：现在零工作情况对应于一个节点，h工作情况对应于一半节点。这个和是O（n logn）就像使用siftUp实现的buildHeap的低效版本一样。但在这种情况下，我们没有选择，因为我们正在尝试排序，我们要求下一个最大的项目被删除下一个。

总之，堆排序的工作是两个阶段的总和：O（n）buildHeap的时间和O（n logn）按顺序删除每个节点，因此复杂性为O（n logn）。你可以证明从信息论的角度来看，对于基于比较的排序，O（n logn）是最好的，因此没有理由对此感到失望，也没有理由期望堆排序能够达到buildHeap所做的O（n）时间限制。