O（n）的证明

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

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

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

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

在构建堆时，假设您采用的是自下而上的方法。

您获取每个元素并将其与子元素进行比较，以检查该元素对是否符合堆规则。因此，叶被免费包含在堆中。那是因为他们没有孩子。向上移动，叶子正上方节点的最坏情况是1次比较（最多只能与一代孩子进行比较）再往上看，他们的直系父母最多可以与两代子女相比。继续朝着相同的方向，在最坏的情况下，您将对根进行log（n）比较。并且log（n）-1用于其直系子代，log（n）-2用于其直系子女，依此类推。所以总结起来，你会得到类似log（n）+{log（n（n）-1}*2+{log（n）-2}*4+…..+1*2^{（logn）-1}，它只是O（n）。