基本上，在构建堆时，只在非叶节点上完成工作。。。所做的工作是减少交换量以满足堆条件。。。换句话说（在最坏的情况下），数量与节点的高度成比例。。。总之，问题的复杂性与所有非叶节点的高度之和成正比。。即（2^h+1-1）-h-1=n--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，我们得到：

现在我们证明构建堆是一个线性操作。

基本上，在构建堆时，只在非叶节点上完成工作。。。所做的工作是减少交换量以满足堆条件。。。换句话说（在最坏的情况下），数量与节点的高度成比例。。。总之，问题的复杂性与所有非叶节点的高度之和成正比。。即（2^h+1-1）-h-1=n--1=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）。

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

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

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

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

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

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

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

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

“构建堆的线性时间界限可以通过计算堆中所有节点的高度之和来显示，这是虚线的最大数量。对于包含N=2^（h+1）–1个节点的高度为h的完美二叉树，节点高度之和为N–h–1。因此它是O（N）。"