假设堆中有N个元素。则其高度为Log（N）

现在您要插入另一个元素，那么复杂性将是：Log（N），我们必须一直向上比较到根。

现在您有N+1个元素&高度=对数（N+1）

利用归纳法可以证明插入的复杂性为∑logi。

现在使用

log a+log b=log ab

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

实际上是O（NlogN）

But

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

在堆上进行了详细的实验之后，我意识到了这一点。

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

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

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

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

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

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

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

向下筛选和向上筛选所需的操作数与节点可能移动的距离成比例。对于向下筛选，它是到树底部的距离，因此向下筛选对于树顶部的节点来说是昂贵的。使用siftUp，工作与到树顶部的距离成正比，因此对于树底部的节点来说，siftUp是昂贵的。尽管在最坏的情况下，两个操作都是O（log n），但在堆中，只有一个节点位于顶层，而一半的节点位于底层。因此，如果我们必须对每个节点应用一个操作，那么我们更倾向于向下筛选而不是向上筛选，这并不奇怪。

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

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

buildHeap的哪个实现更有效？

这两种解决方案都将生成有效的堆。毫不奇怪，更有效的是使用向下筛选的第二个操作。

设h=logn表示堆的高度。向下筛选方法所需的工作由总和给出

(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）。

我们如何证明向下筛选方法的和确实是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（logn）。它通常是通过删除根（堆中剩余的最大项）并用堆中的最后一个项（即叶，因此也是最小项之一）来实现的。这个新的根几乎肯定会违反堆属性，因此必须调用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（nlogn），因此复杂性为O（nlog n）。您可以证明（使用信息理论中的一些想法），对于基于比较的排序，O（n log n）是您所希望的最佳排序，因此没有理由对此感到失望，也没有理由期望堆排序达到buildHeap所能达到的O（n）时间限制。

直观地：

“复杂性应该是O（nLog n）……对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即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），heapify向下过滤log（n）级别。

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

---

理论上：

构建大小为N的堆的总步骤N可以用数学公式表示。

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

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

最后，将x=1/2代入上式得到2。将其代入第一个方程得出：

因此，步骤总数大小为O（n）

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

因此，移动总数：

S=2h*0+2h-1*1+2h-2*2+。。。20*小时

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~2h+h

h=对数（n），2h=n因此S=n+log（n）T（C）=O（n）

我们通过计算每个节点可以进行的最大移动量来获得堆构建的运行时。所以我们需要知道每行中有多少个节点，每个节点离它们的距离有多远。

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

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

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

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

把n带回来，我们得到了2*n，2可以被丢弃，因为它是一个常数，而tada是Siftdown方法最坏的运行时：n。

简短回答

使用Heapify（）构建二进制堆需要O（n）时间。

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

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

在完整的二叉树的骨架中添加所有元素。这需要O（n）时间。现在我们只需要满足min堆属性。由于所有叶元素都没有子元素，因此它们已经满足堆属性。叶元素的总数是ceil（n/2），其中n是树中存在的元素的总数。现在，对于每个内部节点，如果它大于其子节点，则以从下到上的方式将其与最小子节点交换。每个内部节点将花费O（1）时间。注意：我们不会像插入时那样将值交换到根。我们只需交换一次，使该节点上的子树成为一个合适的最小堆。在二进制堆的基于数组的实现中，我们有父级（i）＝ceil（（i-1）/2），i的子级由2*i+1和2*i+2给出。因此，通过观察，我们可以说数组中的最后一个ceil（n/2）元素将是叶节点。深度越大，节点的索引就越多。我们将对阵列[n/2]、阵列[n/2-1]重复步骤4。。。。。数组[0]。通过这种方式，我们确保我们以自下而上的方式完成这项工作。总的来说，我们最终将维护min堆属性。所有n/2元素的步骤4将花费O（n）时间。

因此，使用这种方法进行堆化的总时间复杂度将为O（n）+O（n）~O（n（n）。