堆建立的不同方式的时间复杂度_建堆时间复杂度怎么推导

堆建立分为两种方式：从上往下建堆和从下往上建堆

本文主要分析从下往上建堆，这种方式的时间复杂度更好（O(N)）

如果确定了数组元素只能一个一个给，那我们别无选择，只能从上往下建堆，这个时间复杂度时O(N*logN)

如果可以一次性的把整个数组给我们，类似于数组做堆排序这种，我们就可以使用从下往上的方式建堆，具体的方式是:

（1）先拿到最后一层的节点（堆都是完全二叉树），这些节点的个数是节点总个数N的一半，也就是N/2，先把以这些节点为根的树调整成大根堆，因为只有一个节点无需调整。

（2）接着把以倒数第二层为根的子树调整为大根堆调整倒数第二层、倒数第三层。。。第一层，节点个数分别是N/4, N/8...1

对于整个过程我们做一个分析：

（1）最后一层N/2个元素，无需调整，代价为N/2

（2）倒数第二层N/4个元素，最多调整树的高度，也就是2,所有最多的代价是N/4*2

（3）同理倒数第三层N/8 * 3

（4）倒数第四层N/16*4

。。。。。。

总的代价T(N) = N/2 * 1 + N/4*2 + N/8 * 3 + N/16*4。。。。

那么2*T(N) = N + N/2*2+N/4*3 + N/8*4。。。。

那么T(N) = 2*T(N) - T(N) = N + N/2 + N/4+N/8+N/16.。。。

这个是个等比数列的求和问题，最后收敛于O(N)

关于等比数列的求和问题，大家可以自己百度，也可以参考百度百科：

等比数列求和公式_百度百科

也就是说我们可以计算出了从下往上建堆的时间复杂度是O(N)，但是这个建堆的过程有个前提条件：我们已经拿到了数组的所有数字。