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）的最佳方式是对给定集合使用构建堆算法（排序无关紧要）。

我们可以使用另一个最佳解决方案来构建堆，而不是重复插入每个元素。具体如下：

任意将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，我们得到：

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

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

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

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

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

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

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

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

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

直观地：

“复杂性应该是O（nLog n）……对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即log n级别）过滤一次。”

不完全是。您的逻辑不会产生严格的界限——它会过度估计每个堆的复杂性。如果从下往上构建，插入（heapify）可以比O（log（n））小得多。流程如下：

（步骤1）前n/2个元素位于堆的底行。h=0，因此不需要heapify。

（步骤2）接下来的n/22个元素从底部向上排列在第1行。h=1，将过滤器向下堆1级。

（步骤i）接下来的n/2i元素从底部排i。h=i，将过滤器堆成i级。

（步骤log（n））最后一个n/2log2（n）=1元素从底部向上进入行log（n。h=log（n），heapify向下过滤log（n）级别。

注意：在第一步之后，1/2的元素（n/2）已经在堆中，我们甚至不需要调用heapify一次。此外，请注意，实际上只有一个元素，即根元素，会导致完整的log（n）复杂性。

理论上：

构建大小为N的堆的总步骤N可以用数学公式表示。

在高度i处，我们已经显示（上面）将有n/2i+1个元素需要调用heapify，并且我们知道高度i处的heapify是O（i）。这给出了：

最后求和的解可以通过取众所周知的几何级数方程两边的导数来找到：

最后，将x=1/2代入上式得到2。将其代入第一个方程得出：

因此，步骤总数大小为O（n）

我们知道堆的高度是log（n），其中n是元素的总数当我们执行heapify操作时，最后一级（h）的元素甚至不会移动一步。第二个最后一级（h-1）的元素数为2h-1，它们最多可以移动1级（在堆化期间）。类似地，对于第i层，我们有2i个元素可以移动h-i个位置。

因此，移动总数：

S=2h*0+2h-1*1+2h-2*2+。。。20*小时

S=2h｛1/2+2/22+3/23+…h/2h｝-------------------------------------------------1

这是AGP系列，用于解决两边除以2的问题S/2=2h｛1/22+2/23+…h/2h+1｝-------------------------------------------------2

从1中减去方程式2得到S/2=2h｛1/2+1/22+1/23+…+1/2h+h/2h+1｝S=2h+1{1/2+1/22+1/23+…+1/2h+h/2h+1}

现在1/2+1/22+1/23++1/2h是减小GP，其和小于1（当h趋于无穷大时，和趋于1）。在进一步的分析中，让我们对和取一个上限，即1。

这给出了：S=2h+1｛1+h/2h+1｝=2h+1+h~2h+h

h=对数（n），2h=n因此S=n+log（n）T（C）=O（n）