简短回答

使用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）。

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

从根节点开始，下一行的节点数是前一行的两倍，因此，通过回答节点数可以增加一倍，直到没有剩余节点，我们可以得到树的高度。或者用数学术语来说，树的高度是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。

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

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

O（n）的证明

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

我们可以使用另一个最佳解决方案来构建堆，而不是重复插入每个元素。具体如下：

任意将n个元素放入数组中以尊重堆的形状属性。从最底层开始，向上移动，筛选在heapify down过程中，每个子树向下移动，直到堆属性已还原。

此过程可通过下图进行说明：

接下来，让我们分析一下上述过程的时间复杂性。假设堆中有n个元素，堆的高度为h（对于上图中的堆，高度为3）。那么我们应该有以下关系：

当最后一级只有一个节点时，n=2^h。当树的最后一级被完全填充时，则n＝2^（h+1）。

并且从底部开始作为级别0（根节点是级别h），在级别j中，最多有2^（h-j）个节点。每个节点最多执行j次交换操作。所以在第j级中，操作的总数是j*2^（h-j）。

因此，构建堆的总运行时间与：

如果我们将2^h项考虑在内，那么我们得到：

​正如我们所知，∑j/2是一个收敛到2的级数（详细地说，你可以参考这个wiki）。

使用此功能，我们可以：

根据条件2^h<=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）