向上or向下调整建堆 的时间复杂度的本质区别的讲解

知识点：（N代表节点数，h代表高度）

1：高度为h的满二叉树节点个数N为 2^（h）-1  即N =  2^（h）-1 

2：所以h = log（N+1）

一：向上调整建堆的时间复杂度

时间复杂度即：每层节点的个数×每层节点需要向上调整的次数

例：第一层的节点，有2^0个，并且因为向上调整，所以它不用调整

       第二层的节点，有2^1个，因为向上调整，所以需要向上调整一次

      ...................

1：所以可以得到一个次数与高度h的表达式

2：对此式子使用错位相减法：

3：上式减下式得到：

4：再将其凑成：

解释：

1：前面减一个2^0，后面再加一个2^0，式子没改变

然后对最前面的-2^0和红色部分使用等比求和（先总体提一个负号）使用等比求和得到以下：

由前提的两个公式可知：

 1：N =  2^（h）-1 

2：所以h = log（N+1）

将这两个公式替换进去：

根据大O表示法，可知 时间复杂度为： N*logN

二：向下调整建堆的时间复杂度

同理可知： 

时间复杂度即：每层节点的个数×每层节点需要向上调整的次数

区别在于：向下调整，最后一层不用调整，因为已经到了叶子节点

1：所以：

2：错位相减法可得：

 

3：相减得到：

4：再把式子凑一下：

 

解释：-（h-1）即-h+1，把+1 改成 2^0 和前面的式子进行等比求和

最后得到：

再同理用前面两个公式套进去可得：

 根据大O表示法可得时间复杂度为O（N）

 

所以可知向下调整比向上调整更优秀。