构建堆的时间复杂度如何是 O(n)？
有人可以帮助解释构建堆如何成为 O(n) 复杂度吗？
将一个项插入堆是 O(log n)，插入重复 n/2 次（其余为叶子，不能违反堆属性）。所以，我认为这意味着复杂度应该是 O(n log n)。
换句话说，对于我们“堆积”的每个项目，它有可能必须为到目前为止的堆的每个级别（即 log n 级别）过滤（即筛选）一次。
我错过了什么？
我认为这个话题中隐藏着几个问题：
你如何实现 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 函数获取未排序项的数组并移动它们，直到它们都满足堆属性，从而产生一个有效的堆。使用我们描述的 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)？
一种方法（还有其他分析也有效）是将有限和转换为无限级数，然后使用泰勒级数。我们可以忽略第一项，它是零：
https://i.stack.imgur.com/959f6.png
如果您不确定为什么每个步骤都有效，以下是该过程的理由：
这些项都是正数，因此有限和必须小于无限和。
该级数等于在 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)时间为buildHeap和O(n log n)按顺序移除每个节点，所以复杂度是 O(n log n)。您可以证明（使用信息论中的一些想法）对于基于比较的排序，O(n log n) 是您所希望的最好的，所以没有理由对此感到失望或期望堆排序达到 buildHeap 所做的 O(n) 时间限制。
你的分析是正确的。但是，它并不紧。
解释为什么构建堆是线性操作并不容易，您最好阅读它。
可以看到对算法的精彩分析here。
主要思想是，在 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) 的原因。
siftDown 完成时，Heapify 是 O(n)，但用 siftUp 完成时是 O(n log n)。实际排序（从堆中一个一个地拉出项目）必须使用 siftUp 完成，因此 O(n log n) 也是如此。
i 的节点进行的 # 比较也必须进行 2* log(h-i) 比较，并且也应该考虑@The111。你怎么看？
直观地说：
“复杂度应该是 O(nLog n)……对于我们“堆”的每个项目，到目前为止，它有可能必须为堆的每个级别（即 log n 级别）过滤一次。”
不完全的。您的逻辑不会产生严格的限制——它过度估计了每个 heapify 的复杂性。如果从下往上构建，插入（heapify）可以比 O(log(n)) 少得多。过程如下：
（第 1 步） 前 n/2 个元素位于堆的底行。 h=0，所以不需要 heapify。
（第 2 步） 接下来的 n/22 个元素位于从底部向上的第 1 行。 h=1，heapify 过滤器向下 1 级。
（步骤 i ） 接下来的 n/2i 元素从底部向上排在第 i 行。 h=i，将过滤器向下堆积 i 级。
( Step log(n) ) 最后一个 n/2log2(n) = 1 元素从底部向上进入第 log(n) 行。 h=log(n)，将过滤器向下堆积 log(n) 级。
注意：在第一步之后，元素 (n/2) 中的 1/2 已经在堆中，我们甚至不需要调用 heapify 一次。此外，请注意，实际上只有一个元素（即根）会产生完整的 log(n) 复杂性。
理论上：
构建大小为 n 的堆的总步骤 N 可以用数学方法写出。
在 i 高度，我们已经（上图）展示了需要调用 heapify 的 n/2i+1 个元素，并且我们知道在 i 高度的 heapify 是 O(i)。这给出了：
最后求和的解可以通过对众所周知的几何级数方程两边求导得到：
最后，将 x = 1/2 代入上述方程得到 2。将其代入第一个等式给出：
因此，总步数的大小为 O(n)
如果您通过重复插入元素来构建堆，那将是 O(n log n)。但是，您可以通过以任意顺序插入元素然后应用算法将它们“堆”成正确的顺序（当然取决于堆的类型）来更有效地创建新堆。
有关示例，请参见 http://en.wikipedia.org/wiki/Binary_heap，“构建堆”。在这种情况下，您基本上从树的底层开始工作，交换父节点和子节点，直到满足堆条件。
已经有一些很好的答案，但我想添加一些视觉解释
https://i.stack.imgur.com/rD6R0.jpg
现在，看一下图像，
n/2^1 绿色节点 高度为 0（此处为 23/2 = 12）
n/2^2 红色节点 高度 1（这里 23/4 = 6）
n/2^3 蓝色节点 高度 2 strong>（这里 23/8 = 3）
n/2^4 紫色节点 高度 3（这里 23/16 = 2）
所以有 { 5} 个高度节点 h
要计算时间复杂度，让我们计算 完成的工作量 或 最大迭代次数由每个节点执行
现在可以注意到每个节点可以执行（最多）迭代次数 == 节点的高度
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)
我们知道堆的高度是 log(n)，其中 n 是元素的总数。让我们将其表示为 h 当我们执行 heapify 操作时，最后 level(h) 的元素甚至不会移动一个步。倒数第二层（h-1）的元素数量为 2h-1，它们最多可以移动 1 层（在 heapify 期间）。同样，对于第 i 个级别，我们有 2i 个元素可以移动 hi 位置。
因此总移动次数：
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 正在减少总和小于 1 的 GP（当 h 趋于无穷大时，总和趋于 1）。在进一步分析中，让我们对总和取一个上限，即 1。
这给出： S=2h+1{1+h/2h+1} =2h+1+h ~2h+h
如 h=log(n), 2h=n 因此 S=n+log(n) T(C)=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)。
我们通过计算每个节点可以采取的最大移动来获得堆构建的运行时。所以我们需要知道每行有多少个节点，以及每个节点能走多远。
从根节点开始，下一行的节点数是前一行的两倍，因此通过回答我们多久可以将节点数加倍，直到我们没有任何节点，我们就得到了树的高度。或者用数学术语来说，树的高度是 log2(n)，n 是数组的长度。
为了计算一行中的节点，我们从后面开始，我们知道 n/2 个节点在底部，所以除以 2 我们得到前一行，依此类推。
基于此，我们得到了 Siftdown 方法的公式： (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (log2(n) * 1)
https://i.stack.imgur.com/VOPXG.png
https://i.stack.imgur.com/WzIBL.png
将 n 带回我们有 2 * n，2 可以被丢弃，因为它是一个常数，并且我们有 Siftdown 方法的最坏情况运行时：n。
简答
使用 Heapify() 构建二叉堆将花费 O(n) 时间。
当我们将一个堆中的元素一个一个地添加并在每一步都满足堆属性（最大堆或最小堆）时，那么总时间复杂度将为O(nlogn)。因为二叉堆的一般结构是完全二叉树。因此堆的高度是h = O(logn)。所以堆中元素的插入时间相当于树的高度，即。 O(h) = O(logn)。对于 n 元素，这将花费 O(nlogn) 时间。
现在考虑另一种方法。为了简单起见，我假设我们有一个最小堆。所以每个节点都应该小于它的子节点。
将所有元素添加到完整二叉树的骨架中。这将花费 O(n) 时间。现在我们只需要以某种方式满足最小堆属性。由于所有叶子元素都没有子元素，它们已经满足堆属性。叶元素的总数为 ceil(n/2)，其中 n 是树中存在的元素总数。现在对于每个内部节点，如果它大于其子节点，则以自下而上的方式将其与最小子节点交换。每个内部节点都需要 O(1) 时间。注意：我们不会像在插入中那样将值交换到根。我们只需交换一次，以便以该节点为根的子树是适当的最小堆。在基于数组的二叉堆实现中，我们有 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] 重复第 4 步。通过这种方式，我们确保我们以自下而上的方式执行此操作。总的来说，我们最终将保持最小堆属性。所有 n/2 个元素的第 4 步将花费 O(n) 时间。
所以我们使用这种方法的 heapify 的总时间复杂度将是 O(n) + O(n) ~ O(n)。
在构建堆的情况下，我们从高度 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)
连续插入可以通过以下方式描述：
T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))
通过八哥近似，n! =~ O(n^(n + O(1)))，因此 T =~ O(nlog(n))
希望这会有所帮助，O(n) 的最佳方式是对给定集合使用构建堆算法（排序无关紧要）。
基本上，在构建堆时仅在非叶节点上完成工作......所做的工作是向下交换以满足堆条件的数量......换句话说（在最坏的情况下）数量与高度成正比节点的...总之问题的复杂性与所有非叶节点的高度之和成正比..即 (2^h+1 - 1)-h-1=nh-1=上）
@bcorso 已经展示了复杂性分析的证明。但是为了那些仍在学习复杂性分析的人，我要补充一点：
您最初错误的基础是对语句含义的误解，“插入堆需要 O(log n) 时间”。插入堆确实是 O(log n)，但你必须认识到 n 是插入期间堆的大小。
在将 n 个对象插入堆的上下文中，第 i 次插入的复杂度为 O(log n_i)，其中 n_i 是插入 i 时堆的大小。只有最后一次插入的复杂度为 O (log n)。
假设您在堆中有 N 个元素。那么它的高度将是 Log(N)
现在您要插入另一个元素，那么复杂度将是：Log(N)，我们必须一直比较 UP 到根。
现在你有 N+1 个元素 & height = Log(N+1)
使用induction技术可以证明插入的复杂度为∑logi。
现在使用
日志 a + 日志 b = 日志 ab
这简化为： ∑logi=log(n!)
这实际上是 O(NlogN)
但
我们在这里做错了，因为在所有情况下我们都没有到达顶部。因此，在大多数情况下执行时，我们可能会发现，我们甚至不会爬到树的一半。因此，可以通过使用上面答案中给出的数学来优化此界限以具有另一个更严格的界限。
在对 Heaps 进行了详细的实验和实验之后，我才意识到这一点。
我真的很喜欢 Jeremy west 的解释......这里给出了另一种非常容易理解的方法http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity
因为，buildheap 依赖于使用取决于 heapify 并且使用 shiftdown 方法，这取决于所有节点的高度之和。因此，要找到由 S = summation from i = 0 to i = h of (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)。
“构建堆的线性时间界限，可以通过计算堆中所有节点的高度之和来显示，即虚线的最大数量。对于高度为h的完美二叉树，包含N = 2^( h+1) – 1 个节点，节点高度之和为 N – H – 1。因此它是 O(N)。
我们可以使用另一种最佳解决方案来构建堆，而不是重复插入每个元素。它是这样的：
任意将 n 个元素放入数组中，以尊重堆的形状属性。
从最低层开始向上移动，像 heapify-down 过程一样向下筛选每个子树的根，直到恢复堆属性。
这个过程可以用下图来说明：
https://i.stack.imgur.com/aBxND.png
接下来，我们来分析一下上面这个过程的时间复杂度。假设堆中有n个元素，堆的高度为h（对于上图中的堆，高度为3）。那么我们应该有如下关系：
https://i.stack.imgur.com/aJzPg.png
如果最后一级只有一个节点，则 n = 2^h 。当树的最后一层完全填满时，n = 2^(h+1)。
并且从最底层开始为0级（根节点为h级），在j级中，最多有2^(hj)个节点。每个节点最多进行 j 次交换操作。所以在级别 j 中，操作的总数是 j*2^(hj)。
所以构建堆的总运行时间与：
https://i.stack.imgur.com/Ru8Q9.png
https://i.stack.imgur.com/GH6ig.png
众所周知，∑j/2ʲ是一个收敛到2的级数（具体可以参考this wiki）。
https://i.stack.imgur.com/jqsU0.png
基于条件 2^h <= n，所以我们有：
https://i.stack.imgur.com/HZf3i.png
现在我们证明构建堆是一个线性操作。
siftUp，或者从末尾开始向后移动并调用siftDown。无论您选择哪种方法，您都在选择数组未排序部分中的下一项并执行适当的操作以将其移动到数组有序部分中的有效位置。唯一的区别是性能。