已经有一些很好的答案，但我想补充一点直观的解释

现在，看看图片，有n/2^1个高度为0的绿色节点（此处23/2=12）n/2^2个高度为1的红色节点（此处23/4=6）n/2^3高度为2的蓝色节点（此处23/8=3）n/2^4个紫色节点，高度为3（此处23/16=2）因此高度h有n/2^（h+1）个节点要计算时间复杂度，可以计算每个节点完成的工作量或执行的最大迭代次数现在可以注意到，每个节点都可以执行（atmost）迭代==节点的高度

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）

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

“构建堆的线性时间界限可以通过计算堆中所有节点的高度之和来显示，这是虚线的最大数量。对于包含N=2^（h+1）–1个节点的高度为h的完美二叉树，节点高度之和为N–h–1。因此它是O（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）。

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

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

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

已经有一些很好的答案，但我想补充一点直观的解释

现在，看看图片，有n/2^1个高度为0的绿色节点（此处23/2=12）n/2^2个高度为1的红色节点（此处23/4=6）n/2^3高度为2的蓝色节点（此处23/8=3）n/2^4个紫色节点，高度为3（此处23/16=2）因此高度h有n/2^（h+1）个节点要计算时间复杂度，可以计算每个节点完成的工作量或执行的最大迭代次数现在可以注意到，每个节点都可以执行（atmost）迭代==节点的高度

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）