如何构建堆是O（n）时间复杂度？
有人可以帮助解释如何建立一个堆是O（n）的复杂性？
将一个项目插入一个堆中是O(log n) ，并且该插入重复n / 2次（其余为叶，并且不能违反heap属性）。 所以，我认为这意味着复杂性应该是O(n log n) 。
换句话说，对于我们“堆积”的每个项目，它有可能不得不为每个堆级过滤一次堆（迄今为止）。
我错过了什么？
我认为这个主题有几个问题：
通常，这些问题的答案集中在siftUp和siftDown之间的区别。 在siftUp和siftDown之间做出正确的选择对于获得siftDown O（n）性能buildHeap ，但对于帮助理解buildHeap和heapSort之间的区别并没有帮助。 事实上， buildHeap和heapSort正确实现将只使用siftDown 。 例如， siftUp操作仅用于执行插入到现有堆中的操作，因此它将用于使用二进制堆实现优先级队列。
我已经写了这个来描述最大堆的工作原理。 这是通常用于堆排序或优先级队列的堆的类型，其中较高的值表示较高的优先级。 最小堆也是有用的; 例如，当按升序检索具有整数键的项目或以字母顺序检索字符串时。 原则完全相同; 只需切换排序顺序。
heap属性指定二进制堆中的每个节点必须至少与其两个子节点一样大。 特别是，这意味着堆中最大的项目是根。 筛选和筛选本质上是相反方向的相同操作：移动违规节点，直到满足堆属性：
siftDown一个节点与其最大的子节点进行交换（从而将其向下移动），直到它至少与其下的两个节点一样大。 siftUp一个与其父节点过大的节点进行交换（从而将其向上移动），直到它不大于它上面的节点。 siftDown和siftUp所需的操作数量与节点可能需要移动的距离成正比。 对于siftDown ，它是距树底部的距离，因此对于树顶部的节点， siftDown是昂贵的。 使用siftUp ，工作与距树顶部的距离成比例，所以对于树底部的节点， siftUp是昂贵的。 尽管在最坏的情况下两个操作都是O（log n），但在堆中，只有一个节点位于顶部，而一半节点位于底层。 因此，如果我们必须对每个节点应用一个操作，我们宁愿将siftDown放在siftUp ，这也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 / 2n log n，所以这种方法的复杂性至多为O（n log n）。 但是，我们如何证明siftDown方法的总和确实是O（n）？ 一种方法（也有其他分析也可以）将有限和转换为无穷级数，然后使用泰勒级数。 我们可以忽略第一项，即零：
如果你不确定为什么每个步骤都能正常工作，那么用下面的话来说明这个过程的理由：
由于无限和恰好为n，所以我们得出结论：有限和不大，因此是O（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）。 它通常通过移除根（堆中剩下的最大物品）并将其替换为堆中的最后一个物品来实现，所述物品是叶，因此是最小的物品之一。 这个新的根目录肯定会违反heap属性，所以你必须调用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）是你无论如何可能希望得到的最好的，所以没有理由对此感到失望，或者期望堆排序来实现O（n）的时间绑定buildHeap 。
你的分析是正确的。 但是，它并不严密。
解释为什么构建堆是线性操作并不容易，你应该更好地阅读它。
这里可以看到对算法的一个很好的分析。
主要思想是在build_heap算法中，所有元素的实际heapify成本不是O(log n) 。
当heapify被调用时，运行时间取决于在进程终止之前元素可能在树中向下移动多远。 换句话说，它取决于堆中元素的高度。 在最坏的情况下，元素可能一直下降到叶级。
让我们一起逐级完成所做的工作。
在最底层，有2^(h)节点，但是我们不会在这些节点上调用heapify ，所以工作是0.在下一层有2^(h − 1)节点，每个节点都可能向下移动1级。 在底部的第三层，有2^(h − 2)节点，每个节点可以向下移动2个层次。
正如你所看到的，并不是所有的heapify操作都是O(log n) ，这就是你获得O(n) 。
直观：
“复杂性应该是O（nLog n）...对于我们”堆积“的每个项目，它有可能必须针对堆的每个级别过滤掉一次（这是log n级）。”
不完全的。 你的逻辑不会产生严密的限制 - 它会估计每个堆积的复杂性。 如果从底部开始构建，插入（heapify）可以远小于O(log(n)) 。 过程如下：
（第1步）前n/2元素位于堆的最下一行。 h=0 ，所以heapify是不需要的。
（第2步）接下来的n/22元素从底部开始在第1行上。 h=1 ，heapify过滤器1级降低。
（步骤i）的下一个n/2i元件行去i向上从底部。 h=i ，heapify过滤掉i水平。
（Step log（n））最后一个n/2log2(n) = 1元素从底部向上行log(n) 。 h=log(n) ，heapify过滤log(n)级别。
注意：在第一步之后， 1/2 (n/2)的元素(n/2)已经在堆中，我们甚至不需要调用heapify一次。 另外，请注意，只有一个元素，即根，实际上会导致完整的log(n)复杂性。
从理论上讲：
Total步骤N构建一个大小为n的堆，可以用数学方式写出。
在身高i ，我们已经表明（上图）将会有n/2i+1元素需要调用heapify，并且我们知道heapify在高度i是O(i) 。 这给出：
最后求和的解可以通过取得众所周知的几何级数方程两边的导数来找到：
最后，将x = 1/2插入上面的等式得出2 。 将其插入第一个等式给出：
因此，总步数的大小为O(n)