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

有人可以帮助解释如何build立一个堆是O（n）的复杂性？

插入一个项目到堆中是O(log n) ，并且插入被重复n / 2次（剩下的是叶子，并且不能违反heap属性）。 所以，这意味着复杂性应该是O(n log n) ，我想。

换句话说，对于我们“heapify”的每个项目，它有可能不得不为每个级别过滤一次堆（迄今为止）。

我错过了什么？

Answer 1

你的分析是正确的。 但是，这并不严密。

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

algorithm的一个很好的分析可以在这里看到。

---

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

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

让我们一起逐级完成所做的工作。

在最底层，有2^(h)节点，但是我们没有在这些节点上调用heapify ，所以工作是0.在下一个节点有2^(h − 1)节点，每个节点都可能向下移动1级。 从底层开始，有2^(h − 2)节点，每个节点可以下移2个层次。

正如你所看到的，并不是所有的heapify操作都是O(log n) ，这就是为什么你得到O(n) 。

Answer 2

接受的答案给出了正确的分析，以显示buildHeap在O（n）时间运行。 但是提出的问题是：

“这是一个很好的解释，但是为什么堆类运行在O（n log n）中 ，为什么同样的推理不适用于堆类呢？

在评论中给出了一个回答，表明不同之处在于siftDown vs siftUp ，我认为有点错过了这个观点（或者太简单了，以至于不明显）。 实际上，在实现堆sorting时（尽pipe对于优先队列来说，例如为了实现插入操作），您根本不需要使用siftUp 。

编辑：我修改了我的答案来描述如何最大堆的工作。 这是通常用于堆sorting或优先级队列的堆types，其中较高的值表示较高的优先级。 一个小堆也是有用的; 例如，当以整数键升序检索项目或按字母顺序检索string时。 原则是完全一样的，你只需要切换sorting顺序。

请记住，heap属性指定每个节点必须至less与它的两个子节点一样大。 特别是，这意味着堆中最大的项目是根源。 筛选和筛选本质上是相反的操作：移动一个有问题的节点，直到它满足堆属性：

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

每个操作所需的操作次数与节点可能需要移动的距离成正比。 对于siftDown ，它是距离树的底部的距离，所以siftDown对于树顶部的节点是昂贵的。 使用siftUp ，工作与距树顶部的距离成正比，所以siftUp对于树的底部节点是昂贵的。 尽pipe在最坏的情况下两个操作都是O（log n） ，但在堆中，只有一个节点位于顶部，而一半节点位于底层。 所以，如果我们必须对每个节点应用一个操作，我们应该比siftUp 。

buildHeap函数获取未sorting项目的数组，并移动它们直到它们都满足堆属性。 buildHeap可能需要两种方法。 一个是从堆的顶部开始（数组的开始），并在每个项目上调用siftUp 。 在每一步中，先前筛选的项目（数组中当前项目之前的项目）形成一个有效的堆，筛选下一个项目将其放入堆中的有效位置。 筛选每个节点后，所有项目都满足堆属性。 第二种方法的方向相反：从arrays的末端开始，向前移动。 在每次迭代中，您都要筛选一个项目，直到它位于正确的位置。

这两种解决scheme都将生成一个有效的堆。 问题是： 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 log n） 。 然而， siftDown方法的总和可以通过将其扩展到泰勒级数来表示它的确是O（n） 。 如果有兴趣，我可以编辑我的答案，包括细节。 显然， O（n）是你所希望的最好的。

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

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

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

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

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

总之，堆sorting的工作是两个阶段的总和： O（n）时间为buildHeap和O（n log n）按顺序去除每个节点 ，所以复杂度为O（n log n） 。 你可以certificate（利用信息论中的一些想法），对于基于比较的sorting， O（n log n）是你所希望的最好的，所以没有理由对此失望，或者期望堆sorting来实现O（n）的时间绑定buildHeap 。

Answer 3

直观：

“复杂性应该是O（nLog n）…对于我们”heapify“的每个项目，它有可能不得不为每个级别过滤一个堆到目前为止（这是log n级别）。

不完全的。 你的逻辑不会产生一个紧密的界限 – 它会估计每个堆积的复杂性。 如果从底层开始构build，插入（heapify）可以比O(log(n))less得多。 过程如下：

（第1步） 前n/2元素出现在堆的最下一行。 h=0 ，所以heapify是不需要的。

（步骤2） 接下来的n/2 2元素从底部开始排在第一行。 h=1 ，heapifyfilter1级。

（第一步） 接下来的n/2 i元素从第一行开始。 h=i ，heapify过滤i水平。

（Step log（n） ） 最后n/2 log 2 (n) = 1元素从行底部向上行log(n) 。 h=log(n) ，heapify过滤log(n)级别。

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

---

从理论上讲：

Total步骤N构build一个大小为n的堆，可以用math方法写出来。

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

最后求和的解可以通过取已知几何级数方程两边的导数来求得：

最后，将x = 1/2插入上面的等式得到2 。 把它插入第一个等式给出：

因此，总步数是O(n)

Answer 4

如果通过重复插入元素来构build堆，那么将会是O（n log n）。 但是，通过以任意顺序插入元素，然后应用algorithm将它们“heapify”到正确的顺序（取决于堆的types），可以更高效地创build新的堆。

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

Answer 5

在build立堆的同时，可以说你正在采取自下而上的方法。

1. 你把每个元素和它的孩子比较，以检查这个对是否符合堆规则。 所以，叶子免费包括在堆中。 那是因为他们没有孩子。
2. 向上移动，叶子上方节点的最坏情况将是1比较（最大值时，他们将与仅一代儿童进行比较）
3. 继续往前走，他们的直系亲属最多可以和两代孩子比较。
4. 继续朝相同的方向发展，在最糟糕的情况下，你将有根（log）（n）比较根。 和log（n）-1为其直接子女，log（n）-2为其直系子女等等。
5. 所以总结一下，你得到了log（n）+ {log（n）-1} * 2 + {log（n）-2} * 4 + ….. + 1 * 2 ^ {（ logn）-1}这不过是O（n）。

Answer 6

正如我们所知，堆的高度是log（n） ，其中n是元素的总数。让它表示为h
当我们进行heapify操作时，最后一层（ h ）的元素将不会移动一个步骤。
第二个最后一个等级（ h-1 ）的元素数量是2 ^h-1 ，他们可以在最大1级（heapify）中移动。
同样，对于第i级，我们有2个可以移动hi位置的元素。

因此总的移动次数= S = ^2h * 0 + ^2h-1 * 1 + ^2h-2 * 2 + … 2 ⁰ * h

S = 2 ^h {1/2 + 2/2 ² + ^{3/3 3} + … h / 2 ^h } ———————– ————————– 1
这是AGP系列，解决了这个分裂两边的问题
S / 2 = 2 ^h {1/2 ² + 2/2 ³ + … h / 2 ^{h + 1} } ———————– ————————– 2
从1减去公式2给出
S / 2 = ^2h { 1/2 + 1/2 ² + 1/2 ³ + … + 1 / ^2h + h / ^{2h + 1} }
S = ^{2h + 1} { 1/2 + 1/2 ² + 1/2 ³ + … + 1 / ^2h + h / ^{2h + 1} }
现在1/2 + 1/2 ² + 1/2 ³ + … + 1 / ^2h是总和小于1的递减GP （当h趋于无穷大时，总和趋于1）。 在进一步的分析中，让我们取1的和的上限。
这给出S = ^{2h + 1} {1 + h / ^{2h + 1} }
= 2 ^{h + 1} + h
〜2 ^小时 +小时
如h = log（n） ， 2 ^h = n

因此S = n + log（n）
T（C）= O（n）的

Answer 7

连续插入可以描述如下：

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

通过starling逼近， n! =~ O(n^(n + O(1))) n! =~ O(n^(n + O(1))) ，因此T =~ O(nlog(n))

希望这有助于O(n)使用构build堆algorithm的给定集（sorting无关紧要）的最佳方式。

Answer 8

在构build堆的情况下，我们从高度开始， 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 9

@bcorso已经certificate了复杂性分析的certificate。 但是为了那些还在学习复杂性分析的人，我有这个补充：

你原来的错误的基础是错误地解释了“插入一个堆占用O（log n）时间”的含义。 插入一个堆确实是O（log n），但是你必须认识到在插入过程中n是堆的大小。

在将n个对象插入到堆中的情况下，第i个插入的复杂度为O（log n_i），其中n_i是插入i处堆的大小。 只有最后一个插入的复杂度为O（log n）。

Answer 10

我真的很喜欢杰里米·韦斯特的解释……另外一个很容易理解的方法在这里给出http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

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

Answer 11

“构buildHeap的线性时间界限可以通过计算堆中所有节点的高度总和来表示，即虚线的最大数目，对于包含N = 2 ^（ h + 1） – 1个节点，节点的高度总和为N – H – 1，因此它是O（N）。

Answer 12

基本上，只有在build立一个堆的时候才在非叶节点上完成工作……而且所做的工作是交换下来以满足堆条件的数量…换句话说（在最坏的情况下）数量与高度成正比（2 ^ h + 1 – 1）-h-1 = nh-1 = 1时，所有非叶节点的高度之和成正比，上）

Answer 13

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