有人能解释一下构建堆的复杂性吗？
将项插入到堆中是O（logn），并且插入被重复n/2次（剩余的是叶子，不能违反堆属性）。所以，我认为这意味着复杂性应该是O（n log n）。
换言之，对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即logn级别）过滤（即筛选）一次。
我错过了什么？
当前回答
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）。
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）
我们可以使用另一个最佳解决方案来构建堆，而不是重复插入每个元素。具体如下：
任意将n个元素放入数组中以尊重堆的形状属性。从最底层开始，向上移动，筛选在heapify down过程中，每个子树向下移动，直到堆属性已还原。
此过程可通过下图进行说明：
接下来，让我们分析一下上述过程的时间复杂性。假设堆中有n个元素，堆的高度为h（对于上图中的堆，高度为3）。那么我们应该有以下关系：
当最后一级只有一个节点时，n=2^h。当树的最后一级被完全填充时，则n＝2^（h+1）。
并且从底部开始作为级别0（根节点是级别h），在级别j中，最多有2^（h-j）个节点。每个节点最多执行j次交换操作。所以在第j级中，操作的总数是j*2^（h-j）。
因此，构建堆的总运行时间与：
如果我们将2^h项考虑在内，那么我们得到：
正如我们所知，∑j/2是一个收敛到2的级数（详细地说，你可以参考这个wiki）。
使用此功能，我们可以：
根据条件2^h<=n，我们得到：
现在我们证明构建堆是一个线性操作。
假设堆中有N个元素。则其高度为Log（N）
现在您要插入另一个元素，那么复杂性将是：Log（N），我们必须一直向上比较到根。
现在您有N+1个元素&高度=对数（N+1）
利用归纳法可以证明插入的复杂性为∑logi。
现在使用
log a+log b=log ab
这简化为：∑logi=log（n！）
实际上是O（NlogN）
But
我们在这里做了一些错事，因为在所有情况下，我们都没有达到顶峰。因此，在执行大多数时候，我们可能会发现，我们甚至不会爬到树的一半。因此，可以通过使用上面答案中给出的数学来优化这个界限，使其具有另一个更紧密的界限。
在堆上进行了详细的实验之后，我意识到了这一点。
