建堆
- 向上调整建堆
- 向下调整建堆
- 本质：直接在数组内调整建堆
- 向上调整建堆：把第一个元素当成一个堆，往后一个元素模拟成插入这个堆
- 向下调整建队：把整个数组的元素当成一个树，然后从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
方法1&向上调整建堆
向上调整建堆：把第一个元素当成一个堆，往后一个元素模拟成插入这个堆（每个插入的元素调用向上调整算法）
方法2&向下调整建堆❗
向下调整建队：把整个数组的元素当成一个树，然后从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。（把每棵子树调用向下调整算法）
向下调整建堆：
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？
- 首先把数组元素逻辑上看成一颗树
- 然后调整成堆
- 这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6};
总代码
//建堆 void CreateHeap(int* a, int size) { //方法1向上调整建堆 建堆--建的小堆--降序 建大堆--升序 for (int i = 0; i < size; i++) { AdjustUp(a, i); } //printf("\n"); //方法2向下调整建堆 for (int i = (size - 1 - 1) / 2; i >= 0; i--)//i=0的时候到达根节点此时就是全部向下调整 { Adjustdown(a, size, i);//这里的size不确定，但是肯定比size小所以取最大就size } } int main() { int a[10] = { 2,3,7,5,4,3,9,7,6,10 }; int size = sizeof(a) / sizeof(a[0]); CreateHeap(a, size); for (int i = 0; i < size; i++) { printf("%d ", a[i]); } return 0; }
时间复杂度分析
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
- 建堆的时间复杂度为O(N)。
- 节点N&高度h存在：N=2^h-1
- 对比发现向下：节点少*多的调整；节点多*少的调整
- 向上：节点少*少的调整；节点多*多的调整
- 所以：【向下】调整方法才是最优解
向上调整建堆
向上调整算法的时间复杂度为:
T(h)=-(2^h-1)+2^h*(h-1)+1
T(N)=-N+1+（N+1）* log2(N+1)
≈O（N*logN)
- 向上调整算法的时间复杂度：O（N*logN)
向下调整建堆
向下调整算法的时间复杂度为:
T(h)=2^h-1-h
T(N)=N-log2(N+1) （log2(N+1)可以忽略不计）
≈O（N)
- 向下调整算法的时间复杂度：O（N)
堆排序的时间复杂度
- 建队的时间复杂度：O(N）
- 高度次：logN
- 交换+向下调整（调整高度次）：O（logN*N）=O（N*logN）
- 堆排序的时间复杂度：O（N）+O（N*logN）=O（N*logN）
TopK问题的时间复杂度
- 建小堆/大堆： O（K）
- 比较（总的数据）：忽略
- 交换（最坏程度N次）+向下调整（高度次K个总结点）：O（N*logK)
- TopK问题的时间复杂度：O（K）+O（N*logK)=O（N*logK)
总结
- 假设高度为h，节点个数为N
- N=2^h-1
- h=log2((N+1)
- 高度次的时间复杂度：O（logN)
- AdjustUp向上调整算法：O（logN）
- AdjustDown向下调整算法：O（logN）
- 向上调整建堆：O(N*logN）
- 向下调整建堆：O(N)
- 堆排序的时间复杂度：O(N*logN）
- TopK问题的时间复杂度：O(N*logk)
- 等比数列N*logN。
- 等差数列N*N。
- 且重复数据堆排序不忽略。
下篇重点：链式二叉树
🙂感谢大家的阅读，若有错误和不足，欢迎指正
