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

小开

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

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

小开

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

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

算法的伟大的分析可以看到这里。

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

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

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

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

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

小开

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

我们将每个元素与其子元素进行比较，以检查该元素对是否符合堆规则。因此，叶子免费包含在堆中。那是因为它们没有孩子。
向上移动，叶子正上方节点的最坏情况将是1个比较（最多只能与一代子节点进行比较）
再往上看，他们的直系父母最多可以与两代孩子进行比较。
继续沿同一方向，在最坏的情况下，您将对根进行log（n）比较。它的直接子级为log（n）-1，它们的直接子级为log（n）-2，依此类推。
所以总结一下，你得到像log（n）+{log（n）-1}*2+{log（n）-2}*4+……+1*2^{（logn-1）}这样的东西，它只不过是O（n）。

小开

直观：

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

不完全是。您的逻辑并没有产生严格的限制-它高估了每个堆的复杂性。如果从下往上构建，插入（heapify）可以远小于O(log(n))。过程如下：

（步骤1）第一个#0元素位于堆的底部行。#1，所以不需要heapify。

（步骤2）接下来的#0元素从底部向上排在第1行。#1，堆化过滤器1级。

（步骤我）下一个n/2ⁱ元素从下往上排i。h=i，堆化过滤器i级别。

（步骤log（n））最后一个#0元素从下往上排在第#1行。#2，堆化过滤器#1向下。

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

理论上：

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

在高度i处，我们已经展示了（上面）需要调用heapify的n/2ⁱ⁺¹元素，我们知道高度i的heapify是O(i)。这给出了：

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

最后，将x = 1/2插入上述等式会产生2。将其插入第一个等式得到：

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

小开

最佳答案

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

您如何实现buildHeap以使其在O（n）时间内运行？
当正确实现时，如何显示buildHeap在O（n）时间内运行？
为什么相同的逻辑不能使堆排序在O（n）时间而不是O（n log n）时间运行？

您如何实现`buildHeap`以使其在O（n）时间内运行？

通常，这些问题的答案集中在siftUp和siftDown之间的区别上。在siftUp和siftDown之间做出正确的选择对于buildHeap获得siftDown1性能至关重要，但这并不能帮助人们理解buildHeap和heapSort之间的一般差异。事实上，buildHeap和heapSort的正确实现将siftDown2使用siftDown。siftUp操作只需要在现有堆中执行插入，因此它将用于使用二进制堆实现优先级队列。

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

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

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

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

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

从堆的顶部（数组的开头）开始并对每个项目调用siftUp。在每一步，先前筛选的项目（数组中当前项目之前的项目）形成一个有效的堆，筛选下一个项目将其放置在堆中的有效位置。筛选每个节点后，所有项目都满足堆属性。
或者，从相反的方向开始：从数组的末尾开始，向后移动到前面。在每次迭代中，您都会筛选一个项目，直到它位于正确的位置。

`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）。它通常是通过删除根（堆中剩下的最大项）并将其替换为堆中的最后一项，这是叶，因此是最小项之一。这个新根几乎肯定会违反堆属性，所以你必须调用siftDown，直到你将它移回可接受的位置。这也有将下一个最大项向上移动到根的效果。请注意，与buildHeap相反，对于大多数节点，我们从树的底部调用siftDown，我们现在在每次迭代中从树的顶部调用siftDown！虽然这棵树在缩小但它缩小得不够快：树的高度保持不变，直到你删除了前半部分节点（当你完全清除底层时）。然后在下一个季度，高度是h-1。所以第二阶段的总工作是

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

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

总之，堆排序的工作是两个阶段的总和：O（n）构建堆和O（n log n）按顺序删除每个节点的时间，因此复杂度为O（n log n）。您可以证明（使用信息论的一些想法），对于基于比较的排序，O（n log n）是您所希望的最好的，所以没有理由对此感到失望，或者期望堆排序达到buildHeap所做的O（n）时间范围。

小开

连续插入可以描述为：

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

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

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

小开

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

因为，构建堆依赖于使用依赖于堆，而使用了依赖于所有节点高度之和的Shiftdown方法。因此，要找到由以下给出的节点高度之和S=从i=0到i=h的求和（2^i*（h-i）），其中h=logns是树的高度解s，我们得到s=2^（h+1）-1-（h+1）因为，n=2^（h+1）-1s=n-h-1=n-logn-1s=O（n），所以构建堆的复杂度是O（n）。

小开

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

小开

基本上，在构建堆时只在非叶节点上完成工作……所做的工作是为了满足堆条件而向下交换的数量……换句话说（在最坏的情况下）数量与节点的高度成正比……所有问题的复杂性都与所有非叶节点的高度之和成正比……这是（2^h+1-1）-h-1=n-h-1=O（n）

小开

在构建堆的情况下，我们从高度开始，logn-1（其中logns是n个元素的树的高度）。对于存在于高度'h'的每个元素，我们以max upto（logn-h）高度向下。

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

小开

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

因此总移动次数：

S=2^h*0+2^<强>h-1*1+2^<强>h-2*2+…2^<说明>0*h

S=2^h{1/2+2/2^<修>2+3/2^<修>3+… h/2^h} -------------------------------------------------1

这是AGP级数，要解决这个问题，两边都除以2
S/2=2^h{1/2²+2/2^<修>3+… h/2^h+1} -------------------------------------------------2

从1中减去等式2得到
S/2=2^h{1/2+1/2^<修>2+1/2^<修>3+…+1/2^h+h/2^h+1^h0
S=2^h+1{1/2+1/2^<修>2+1/2^<修>3+…+1/2^h+h/2^h+1}

现在1/2+1/2^<修>2+1/2^<修>3+…+1/2^h正在递减GP，其总和小于1（当h趋向无穷大时，总和趋向于1）。在进一步的分析中，让我们取总和的上限为1。

这给出了：
S=2^h+1{1+h/2^h+1}
=2^h+1+h
~2^h+h

作为h=log（n），2^h=n

所以S=n+log（n）
T（C）=O（n）

小开

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

你最初错误的基础是对语句含义的误解，“插入堆需要O（log n）时间”。插入堆确实是O（log n），但你必须认识到n是堆在插入的大小。

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

小开

O（n）的证明

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

小开

假设堆中有N个元素。那么它的高度将是日志（N）

现在你想插入另一个元素，那么复杂性将是：日志（N），我们必须一直将UP与根进行比较。

现在你有n+1个元素和高度=日志（N+1）

使用<强>归纳技术可以证明插入的复杂度为SI logi。

现在使用

log a+log b=log ab

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

实际上是O（NlogN）

但是

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

在堆上进行了一个细节和实验后，我意识到了这一点。

小开

已经有了一些很好的答案，但我想补充一点视觉解释

输入图片描述

现在，看一下图像，有
n/2^1绿色节点和高度0（这里23/2=12）
n/2^2红色节点和高度1（这里23/4=6）
n/2^3蓝色节点和高度2（这里23/8=3）
n/2^4紫色节点和高度3（这里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/2^4 * 3 (heapify will perform atmost three swaps for each purple node)

所以对于任何高度为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）

小开

我们通过计算每个节点可以采取的最大移动来获取堆构建的运行时。所以我们需要知道每行有多少个节点，每个节点可以走多远。

从根节点开始，下一行的节点数是前一行的两倍，因此通过回答我们多久可以将节点数翻倍，直到我们没有任何节点离开，我们得到树的高度。或者用数学术语来说，树的高度是log2（n），n是数组的长度。

为了计算一行中的节点，我们从后面开始，我们知道n/2个节点在底部，所以除以2，我们得到前一行，依此类推。

基于此，我们得到Siftdown方法的公式：（0*n/2）+（1*n/4）+（2*n/8）+…+（log2（n）*1）

最后一次联机中的术语是树的高度乘以根处的一个节点，第一次联机中的术语是底部行中的所有节点乘以它们可以移动的长度，0。Smart中的相同公式：

把n带回来，我们有2*n，2可以被丢弃，因为它是一个常量，tada我们有Siftdown方法的最坏情况运行时：n。

小开

简短回答

构建二进制堆将花费O(n)和Heapify()的时间。

当我们一个接一个地在堆中添加元素并在每一步都满足堆属性（最大堆或最小堆）时，总时间复杂度将为O(nlogn)。因为二进制堆的一般结构是一个完整的二叉树。因此堆的高度是h = O(logn)。所以一个元素在堆中的插入时间相当于树的高度。O(h) = O(logn)。对于n个元素，这将花费O(nlogn)时间。

现在考虑另一种方法。为了简单起见，我假设我们有一个最小堆。所以每个节点都应该小于它的子节点。

添加完整二叉树骨架中的所有元素。这将花费O(n)时间。
现在我们只需要以某种方式满足min-heap属性。
由于所有叶元素都没有子元素，因此它们已经满足堆属性。叶元素的总数为ceil(n/2)，其中n是树中存在的元素总数。
现在对于每个内部节点，如果它大于其子节点，则以自下而上的方式将其与最小子节点交换。每个内部节点将花费O(1)时间。Note:我们不会像插入中那样将值向上交换到根。我们只是交换一次，以便根植于该节点的子树是一个正确的最小堆。
在基于数组的二进制堆实现中，我们有parent(i) = ceil((i-1)/2)，i的子级由2*i + 1和2*i + 2给出。因此，通过观察，我们可以说数组中的最后ceil(n/2)元素将是叶节点。深度越大，节点的索引越多。我们将对array[n/2], array[n/2 - 1].....array[0]重复Step 4。通过这种方式，我们确保我们以自下而上的方法做到这一点。总的来说，我们最终将保持min heap属性。
所有n/2元素的第4步将花费O(n)时间。