有人能解释一下构建堆的复杂性吗？
将项插入到堆中是O（logn），并且插入被重复n/2次（剩余的是叶子，不能违反堆属性）。所以，我认为这意味着复杂性应该是O（n log n）。
换言之，对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即logn级别）过滤（即筛选）一次。
我错过了什么？
当前回答
@bcorso已经证明了复杂性分析的证据。但为了那些还在学习复杂性分析的人，我想补充一下：
您最初错误的基础是对语句含义的误解，“插入堆需要O（logn）时间”。插入到堆中确实是O（logn），但您必须认识到n是插入过程中堆的大小。
在向堆中插入n个对象的情况下，第i次插入的复杂性为O（logn_i），其中n_i是插入i时堆的大小。只有最后一次插入的复杂度为O（log 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）。
已经有一些很好的答案，但我想补充一点直观的解释
现在，看看图片，有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）
连续插入可通过以下方式描述：
T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))
通过starling近似，n！=~O（n^（n+O（1））），因此T=~O（nlog（n））
希望这有帮助，O（n）的最佳方式是对给定集合使用构建堆算法（排序无关紧要）。
O（n）的证明
这个证明并不花哨，而且很简单，我只证明了完全二叉树的情况，结果可以推广到完全二叉。
@bcorso已经证明了复杂性分析的证据。但为了那些还在学习复杂性分析的人，我想补充一下：
您最初错误的基础是对语句含义的误解，“插入堆需要O（logn）时间”。插入到堆中确实是O（logn），但您必须认识到n是插入过程中堆的大小。
在向堆中插入n个对象的情况下，第i次插入的复杂性为O（logn_i），其中n_i是插入i时堆的大小。只有最后一次插入的复杂度为O（log n）。
