有人能解释一下构建堆的复杂性吗？
将项插入到堆中是O（logn），并且插入被重复n/2次（剩余的是叶子，不能违反堆属性）。所以，我认为这意味着复杂性应该是O（n log n）。
换言之，对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即logn级别）过滤（即筛选）一次。
我错过了什么？
当前回答
假设堆中有N个元素。则其高度为Log（N）
现在您要插入另一个元素，那么复杂性将是：Log（N），我们必须一直向上比较到根。
现在您有N+1个元素&高度=对数（N+1）
利用归纳法可以证明插入的复杂性为∑logi。
现在使用
log a+log b=log ab
这简化为：∑logi=log（n！）
实际上是O（NlogN）
But
我们在这里做了一些错事，因为在所有情况下，我们都没有达到顶峰。因此，在执行大多数时候，我们可能会发现，我们甚至不会爬到树的一半。因此，可以通过使用上面答案中给出的数学来优化这个界限，使其具有另一个更紧密的界限。
在堆上进行了详细的实验之后，我意识到了这一点。
其他回答
如果通过重复插入元素来构建堆，那么它将是O（n log n）。然而，通过以任意顺序插入元素，然后应用算法将它们“堆”成正确的顺序（当然取决于堆的类型），可以更有效地创建新的堆。
看见http://en.wikipedia.org/wiki/Binary_heap，例如“构建堆”。在这种情况下，您基本上从树的底层开始工作，交换父节点和子节点，直到满足堆条件。
“构建堆的线性时间界限可以通过计算堆中所有节点的高度之和来显示，这是虚线的最大数量。对于包含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）。
基本上，在构建堆时，只在非叶节点上完成工作。。。所做的工作是减少交换量以满足堆条件。。。换句话说（在最坏的情况下），数量与节点的高度成比例。。。总之，问题的复杂性与所有非叶节点的高度之和成正比。。即（2^h+1-1）-h-1=n--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)
