有人能解释一下构建堆的复杂性吗？
将项插入到堆中是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
我们在这里做了一些错事，因为在所有情况下，我们都没有达到顶峰。因此，在执行大多数时候，我们可能会发现，我们甚至不会爬到树的一半。因此，可以通过使用上面答案中给出的数学来优化这个界限，使其具有另一个更紧密的界限。
在堆上进行了详细的实验之后，我意识到了这一点。
其他回答
在构建堆时，假设您采用的是自下而上的方法。
您获取每个元素并将其与子元素进行比较，以检查该元素对是否符合堆规则。因此，叶被免费包含在堆中。那是因为他们没有孩子。向上移动，叶子正上方节点的最坏情况是1次比较（最多只能与一代孩子进行比较）再往上看，他们的直系父母最多可以与两代子女相比。继续朝着相同的方向，在最坏的情况下，您将对根进行log（n）比较。并且log（n）-1用于其直系子代，log（n）-2用于其直系子女，依此类推。所以总结起来，你会得到类似log（n）+{log（n（n）-1}*2+{log（n）-2}*4+…..+1*2^{（logn）-1}，它只是O（n）。
“构建堆的线性时间界限可以通过计算堆中所有节点的高度之和来显示，这是虚线的最大数量。对于包含N=2^（h+1）–1个节点的高度为h的完美二叉树，节点高度之和为N–h–1。因此它是O（N）。"
你的分析是正确的。然而，它并不紧密。
要解释为什么构建堆是一个线性操作并不容易，您应该更好地阅读它。
这里可以看到对算法的详细分析。
主要思想是，在build_heap算法中，所有元素的实际堆化成本不是O（logn）。
当调用heapify时，运行时间取决于进程终止之前元素在树中向下移动的距离。换句话说，它取决于堆中元素的高度。在最坏的情况下，元素可能会一直下降到叶级别。
让我们一级一级地计算完成的工作。
在最底层，有2^（h）个节点，但我们没有对这些节点调用heapify，因此功为0。在下一级有2^（h−1）个节点，每个节点可能向下移动一级。在从底部开始的第3层，有2^（h−2）个节点，每个节点可能向下移动2层。
正如您所看到的，并不是所有的heapify操作都是O（logn），这就是为什么您会得到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）的证明
这个证明并不花哨，而且很简单，我只证明了完全二叉树的情况，结果可以推广到完全二叉。
