有人能解释一下构建堆的复杂性吗？
将项插入到堆中是O（logn），并且插入被重复n/2次（剩余的是叶子，不能违反堆属性）。所以，我认为这意味着复杂性应该是O（n log n）。
换言之，对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即logn级别）过滤（即筛选）一次。
我错过了什么？
当前回答
在构建堆的情况下，我们从高度开始，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)
其他回答
你的分析是正确的。然而，它并不紧密。
要解释为什么构建堆是一个线性操作并不容易，您应该更好地阅读它。
这里可以看到对算法的详细分析。
主要思想是，在build_heap算法中，所有元素的实际堆化成本不是O（logn）。
当调用heapify时，运行时间取决于进程终止之前元素在树中向下移动的距离。换句话说，它取决于堆中元素的高度。在最坏的情况下，元素可能会一直下降到叶级别。
让我们一级一级地计算完成的工作。
在最底层，有2^（h）个节点，但我们没有对这些节点调用heapify，因此功为0。在下一级有2^（h−1）个节点，每个节点可能向下移动一级。在从底部开始的第3层，有2^（h−2）个节点，每个节点可能向下移动2层。
正如您所看到的，并不是所有的heapify操作都是O（logn），这就是为什么您会得到O（n）。
@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）。
简短回答
使用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）。
在构建堆的情况下，我们从高度开始，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)
