向上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）
所以可知向下调整比向上调整更优秀。