基本上，在构建堆时，只在非叶节点上完成工作。。。所做的工作是减少交换量以满足堆条件。。。换句话说（在最坏的情况下），数量与节点的高度成比例。。。总之，问题的复杂性与所有非叶节点的高度之和成正比。。即（2^h+1-1）-h-1=n--1=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，我们得到：

现在我们证明构建堆是一个线性操作。

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

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

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

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

在构建堆的情况下，我们从高度开始，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)

@bcorso已经证明了复杂性分析的证据。但为了那些还在学习复杂性分析的人，我想补充一下：

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

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