有人能解释一下构建堆的复杂性吗？
将项插入到堆中是O（logn），并且插入被重复n/2次（剩余的是叶子，不能违反堆属性）。所以，我认为这意味着复杂性应该是O（n log n）。
换言之，对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即logn级别）过滤（即筛选）一次。
我错过了什么？
当前回答
“构建堆的线性时间界限可以通过计算堆中所有节点的高度之和来显示，这是虚线的最大数量。对于包含N=2^（h+1）–1个节点的高度为h的完美二叉树，节点高度之和为N–h–1。因此它是O（N）。"
其他回答
假设堆中有N个元素。则其高度为Log（N）
现在您要插入另一个元素，那么复杂性将是：Log（N），我们必须一直向上比较到根。
现在您有N+1个元素&高度=对数（N+1）
利用归纳法可以证明插入的复杂性为∑logi。
现在使用
log a+log b=log ab
这简化为：∑logi=log（n！）
实际上是O（NlogN）
But
我们在这里做了一些错事，因为在所有情况下，我们都没有达到顶峰。因此，在执行大多数时候，我们可能会发现，我们甚至不会爬到树的一半。因此，可以通过使用上面答案中给出的数学来优化这个界限，使其具有另一个更紧密的界限。
在堆上进行了详细的实验之后，我意识到了这一点。
O（n）的证明
这个证明并不花哨，而且很简单，我只证明了完全二叉树的情况，结果可以推广到完全二叉。
@bcorso已经证明了复杂性分析的证据。但为了那些还在学习复杂性分析的人，我想补充一下：
您最初错误的基础是对语句含义的误解，“插入堆需要O（logn）时间”。插入到堆中确实是O（logn），但您必须认识到n是插入过程中堆的大小。
在向堆中插入n个对象的情况下，第i次插入的复杂性为O（logn_i），其中n_i是插入i时堆的大小。只有最后一次插入的复杂度为O（log n）。
我们知道堆的高度是log（n），其中n是元素的总数当我们执行heapify操作时，最后一级（h）的元素甚至不会移动一步。第二个最后一级（h-1）的元素数为2h-1，它们最多可以移动1级（在堆化期间）。类似地，对于第i层，我们有2i个元素可以移动h-i个位置。
因此，移动总数：
S=2h*0+2h-1*1+2h-2*2+。。。20*小时
S=2h｛1/2+2/22+3/23+…h/2h｝-------------------------------------------------1
这是AGP系列，用于解决两边除以2的问题S/2=2h｛1/22+2/23+…h/2h+1｝-------------------------------------------------2
从1中减去方程式2得到S/2=2h｛1/2+1/22+1/23+…+1/2h+h/2h+1｝S=2h+1{1/2+1/22+1/23+…+1/2h+h/2h+1}
现在1/2+1/22+1/23++1/2h是减小GP，其和小于1（当h趋于无穷大时，和趋于1）。在进一步的分析中，让我们对和取一个上限，即1。
这给出了：S=2h+1｛1+h/2h+1｝=2h+1+h~2h+h
h=对数（n），2h=n因此S=n+log（n）T（C）=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)
