如何构建堆是O（n）时间复杂度？

Question

有人可以帮助解释如何构建堆是O（n）复杂性？

将项插入堆是O(log n)，插入重复n / 2次（其余部分是叶子，并且不能违反堆属性）。所以，这意味着复杂性应该是O(n log n)，我想。

换句话说，对于我们“堆积”的每个项目，它有可能必须针对堆的每个级别过滤掉一次（这是log n级别）。

我错过了什么？

Answer 1

我认为这个主题有几个问题：

• 你如何实现buildHeap所以它在O（n）时间运行？
• 如何正确实施buildHeap在O（n）时间运行？
• 为什么同样的逻辑不能使堆排序在O（n）时间而不是O（n log n）中运行？

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

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

我写这篇文章来描述最大堆如何工作。这是通常用于堆排序或优先级队列的堆类型，其中较高的值表示较高的优先级。最小堆也很有用;例如，当按升序检索具有整数键的项目或按字母顺序检索字符串时。原则完全一样;只需切换排序顺序即可。

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

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

siftDown和siftUp所需的操作次数与节点可能必须移动的距离成比例。对于siftDown，它是到树底部的距离，因此siftDown对于树顶部的节点来说是昂贵的。使用siftUp，工作与到树顶部的距离成比例，因此siftUp对于树底部的节点来说是昂贵的。虽然在最坏的情况下两个操作都是O（log n），但在堆中，只有一个节点位于顶部，而一半节点位于底层。因此，如果我们必须对每个节点应用一个操作，我们宁愿选择siftDown而不是siftUp也不应该太令人惊讶。

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

1. 从堆的顶部开始（数组的开头）并在每个项目上调用siftUp。在每一步中，先前筛选的项（数组中当前项之前的项）形成有效堆，并筛选下一项将其置于堆中的有效位置。筛选每个节点后，所有项都满足堆属性。
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/2 n log n，因此这种方法最多具有复杂度O（n log n）。

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

一种方法（还有其他分析也有效）是将有限和转换为无限级数，然后使用泰勒级数。我们可能会忽略第一项，即零：

如果您不确定为什么每个步骤都有效，那么这个过程的理由是：

• 这些术语都是正数，因此有限和必须小于无限和。
• 该系列等于在x = 1/2时评估的幂级数。
• 对于f（x）= 1 /（1-x），该幂级数等于（恒定次数）泰勒级数的导数。
• x = 1/2在该泰勒级数的收敛区间内。
• 因此，我们可以用1 /（1-x）代替泰勒级数，进行微分，并评估找到无穷级数的值。

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

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

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

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

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

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

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

总之，堆排序的工作是两个阶段的总和：buildHeap的O（n）时间和O（n log n）按顺序删除每个节点，因此复杂度为O（n log n）。您可以证明（使用信息理论中的一些想法），对于基于比较的排序，O（n log n）是您可能希望的最佳方式，因此没有理由对此感到失望或期望堆排序实现O（n）时间限制buildHeap。

Answer 2

基本上，在构建堆时，仅在非叶节点上完成工作......并且完成的工作是交换以满足堆条件的量...换句话说（在最坏的情况下）该量与高度成比例节点......所有问题的复杂性都与所有非叶节点的高度之和成正比..这是（2 ^ h + 1 - 1）-h-1 = nh-1 =上）

Answer 3

@bcorso已经证明了复杂性分析的证明。但是为了那些仍在学习复杂性分析的人，我要补充一下：

原始错误的基础是由于对语句含义的误解，“插入堆需要O（log n）时间”。插入堆确实是O（log n），但您必须认识到n是插入期间堆的大小。

在将n个对象插入堆中的上下文中，第i个插入的复杂性是O（log n_i），其中n_i是插入i时堆的大小。只有最后一次插入的复杂度为O（log n）。

Answer 4

Proof of O(n)

证明不是很花哨，而且很简单，我只证明了完整二叉树的情况，结果可以推广到完整的二叉树。

Answer 5

我真的很喜欢Jeremy west的解释......这里给出了另一种非常容易理解的方法http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

因为，buildheap依赖于使用取决于heapify和shiftdown方法，它取决于所有节点的高度之和。因此，要找到S =由i = 0到i = h（2 ^ i *（hi））求和的节点高度之和，其中h = logn是求解s的树的高度，我们得到s = 2 ^（h + 1） - 1 - （h + 1）因为，n = 2 ^（h + 1） - 1 s = n - h - 1 = n-logn - 1 s = O（n），所以buildheap的复杂性是O（n）。

Answer 6

“构建堆的线性时间界限，可以通过计算堆中所有节点的高度之和来显示，这是最大虚线数。对于高度为h的完美二叉树，包含N = 2 ^（ h + 1） - 1个节点，节点高度之和为N-H-1。因此它是O（N）。“

Answer 7

让我们假设你在堆中有N个元素。然后它的高度将是Log（N）

现在你要插入另一个元素，那么复杂性将是：Log（N），我们必须比较UP到root的所有方式。

现在你有N + 1个元素＆height = Log（N + 1）

使用induction技术可以证明插入的复杂性是Σlogi。

现在用

记录a + log b = log ab

这简化为：Σlogi= log（n！）

这实际上是O（NlogN）

但

我们在这里做错了，因为在所有情况下我们都没有达到顶峰。因此，在大多数时间执行时，我们可能会发现，我们甚至不会走到树的一半。因此，通过使用上面答案中给出的数学，可以优化此界限以使另一个更紧密的界限。

在对Heaps进行详细介绍和实验之后，我意识到了这一认识。

Answer 8

认为你犯了一个错误。看看这个：http://golang.org/pkg/container/heap/构建一个堆isn'y O（n）。但是，插入是O（lg（n）。我假设初始化为O（n），如果你设置堆大小b / c，堆需要分配空间并设置数据结构。如果你有n个项目要放然后是，每个插入是lg（n）并且有n个项目，所以你得到n * lg（n）

Answer 9

你的分析是正确的。但是，它并不紧张。

解释为什么构建堆是一个线性操作并不是很容易，你应该更好地阅读它。

对here的算法进行了很好的分析。

---

主要的想法是，在build_heap算法中，实际的heapify成本不是O(log n)for所有元素。

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

让我们逐级计算完成的工作。

在最底层，有2^(h)nodes，但我们不会在任何这些上调用heapify，因此工作为0.在下一级别有2^(h − 1)节点，每个节点可能向下移动1级。在底部的第3层，有2^(h − 2)节点，每个节点可能向下移动2个级别。

你可以看到并非所有的堆化操作都是O(log n)，这就是你获得O(n)的原因。

Answer 10

直观：

“复杂性应该是O（nLog n）...对于我们”堆积“的每个项目，它有可能必须为目前为止的堆的每个级别过滤掉一次（这是log n级别）。”

不完全的。你的逻辑不会产生严格的限制 - 它估计每个堆的复杂性。如果从下往上构建，插入（heapify）可能比O(log(n))小得多。过程如下：

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

（步骤2）下一个n/22元素从底部向上排1。 h=1，堆积过滤器1级。

（步骤i）下一个n/2i元素从底部向上排成i。 h=i，堆积过滤器i水平下降。

（步骤log（n））最后一个n/2log2(n) = 1元素从底部向上行log(n)。 h=log(n)，堆积过滤器log(n)水平下降。

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

---

从理论上讲：

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

在高度i，我们已经显示（上图）将有n/2i+1元素需要调用heapify，并且我们知道堆积在高度i是O(i)。这给出了：

通过得到众所周知的几何级数方程两边的导数，可以找到最后求和的解：

最后，将x = 1/2插入上面的等式产生2。将其插入第一个等式给出：

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

Answer 11

如果通过重复插入元素来构建堆，那么它将是O（n log n）。但是，您可以通过以任意顺序插入元素然后应用算法将它们“堆积”到正确的顺序（当然，取决于堆的类型），从而更有效地创建新堆。

有关示例，请参阅http://en.wikipedia.org/wiki/Binary_heap，“构建堆”。在这种情况下，您基本上从树的底层开始，交换父节点和子节点，直到满足堆条件。

Answer 12

我们知道堆的高度是log（n），其中n是元素的总数。让它表示为h 当我们执行heapify操作时，最后一级（h）的元素甚至不会移动一步。 倒数第二级（h-1）的元素数量为2h-1，它们可以在最大1级移动（在堆化期间）。 类似地，对于第i个级别，我们有2i个元素可以移动h-i个位置。

因此总移动次数= S = 2h * 0 + 2h-1 * 1 + 2h-2 * 2 + ... 20 * h

S = 2h {1/2 + 2/22 + 3/23 + ...... h / 2h} --------------------------- ---------------------- 1 这是AGP系列，解决这个问题，双方分别为2 S / 2 = 2h {1/22 + 2/23 + ... h / 2h + 1} --------------------------- ---------------------- 2 从1中减去等式2给出 S / 2 = 2h {1/2 + 1/22 + 1/23 + ... + 1 / 2h + h / 2h + 1} S = 2h + 1 {1/2 + 1/22 + 1/23 + ... + 1 / 2h + h / 2h + 1} 现在1/2 + 1/22 + 1/23 + ... + 1 / 2h正在减小GP，其总和小于1（当h趋于无穷大时，总和趋于1）。在进一步分析中，让我们取总和为1的上限。 得到S = 2h + 1 {1 + h / 2h + 1} = 2H + 1 + H 〜2小时+ H 如h = log（n），2h = n 因此S = n + log（n） T（C）= O（n）的

Answer 13

在构建堆时，假设您采用自下而上的方法。

1. 您将每个元素与其子元素进行比较，以检查该元素是否符合堆规则。因此，叶子可以免费包含在堆中。那是因为他们没有孩子。
2. 向上移动，叶子正上方的节点的最坏情况将是1比较（在最大值它们将与仅仅一代的孩子进行比较）
3. 进一步向上，他们的直系父母最多可以与两代孩子进行比较。
4. 继续朝着相同的方向，在最坏的情况下，您将对根进行log（n）比较。并为其直接子节点记录（n）-1，为其直接子节点记录log（n）-2，依此类推。
5. 总而言之，你得到的东西就像log（n）+ {log（n）-1} * 2 + {log（n）-2} * 4 + ..... + 1 * 2 ^ {（ logn）-1}这只是O（n）。

Answer 14

已经有一些很好的答案，但我想添加一些视觉解释

现在，看看图像，有 高度为0的n/2^1绿色节点（此处23/2 = 12） 高度为1的n/2^2红色节点（此处为23/4 = 6） 高度为2的n/2^3蓝色节点（此处23/8 = 3） 高度为3的n/2^4紫色节点（此处23/16 = 2） 所以高度为h的n/2^(h+1)节点 要查找时间复杂度，可以计算每个节点执行的工作量或最大迭代次数 现在可以注意到，每个节点可以执行（最近）迭代==节点的高度

Green = n/2^1 * 0 (no iterations since no children)  
red   = n/2^2 * 1 (*heapify* will perform atmost one swap for each red node)  
blue  = n/2^3 * 2 (*heapify* will perform atmost two swaps for each blue node)  
purple = n/4^3 * 3  

所以对于任何高度为h的节点，最大工作量是n / 2 ^（h + 1）* h

现在完成的工作是

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)  
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

现在对于h的任何值，序列

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

永远不会超过1 因此，构建堆的时间复杂度永远不会超过O（n）

Answer 15

在构建堆的情况下，我们从height开始，logn -1（其中logn是n个元素的树的高度）。对于高度为“h”的每个元素，我们将最大值达到（logn -h）高度。

    So total number of traversal would be:-
    T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn
    T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn)))
    T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn
     and according to the [sources][1]
    function in the bracket approaches to 2 at infinity.
    Hence T(n) ~ O(n)

Answer 16

连续插入可以通过以下方式描述：

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

通过椋鸟近似，n! =~ O(n^(n + O(1)))，因此T =~ O(nlog(n))

希望这有所帮助，O(n)为给定集合使用构建堆算法的最佳方式（排序无关紧要）。