假设堆中有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，例如“构建堆”。在这种情况下，您基本上从树的底层开始工作，交换父节点和子节点，直到满足堆条件。

你的分析是正确的。然而，它并不紧密。

要解释为什么构建堆是一个线性操作并不容易，您应该更好地阅读它。

这里可以看到对算法的详细分析。

主要思想是，在build_heap算法中，所有元素的实际堆化成本不是O（logn）。

当调用heapify时，运行时间取决于进程终止之前元素在树中向下移动的距离。换句话说，它取决于堆中元素的高度。在最坏的情况下，元素可能会一直下降到叶级别。

让我们一级一级地计算完成的工作。

在最底层，有2^（h）个节点，但我们没有对这些节点调用heapify，因此功为0。在下一级有2^（h−1）个节点，每个节点可能向下移动一级。在从底部开始的第3层，有2^（h−2）个节点，每个节点可能向下移动2层。

正如您所看到的，并不是所有的heapify操作都是O（logn），这就是为什么您会得到O（n）。

在构建堆时，假设您采用的是自下而上的方法。

您获取每个元素并将其与子元素进行比较，以检查该元素对是否符合堆规则。因此，叶被免费包含在堆中。那是因为他们没有孩子。向上移动，叶子正上方节点的最坏情况是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）。"

简短回答

使用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）。