目录

一、建堆方式

1.堆的实现中——HeapPush()插入建堆

2.手动建堆——利用AdjustUp()向上调整建堆

3.手动建堆——利用AdjustDown()向下调整建堆

二、手动建堆时间复杂度对比分析

1.向上调整建堆时间复杂度O(N*logN)

2.向下调整建堆时间复杂度O(N)

---

一、建堆方式

1.堆的实现中——HeapPush()插入建堆

让我们回顾一下在堆的实现部分，我们是如何建堆的。

详细实现过程，可以回顾博客：【数据结构】 二叉树的顺序结构——堆的实现-CSDN博客

 

回顾一下 HeapPush()函数的实现

2.手动建堆——利用AdjustUp()向上调整建堆

在堆的应用中堆排序、top-k问题都用到了AdjustUp()手动建堆，该函数两个参数，一是存储空间首地址，二是孩子节点下标child，孩子结点下标和存储空间下标一一对应，用循环变量控制即可。

3.手动建堆——利用AdjustDown()向下调整建堆

在堆的应用中，我们为了少写一个AdjustUp()函数,所以一般用向上调整建堆。

向下调整建堆要满足左右子树都是堆。

❓但是实际手动建堆的情况，左右子树都不满足堆怎么办，该如何考虑：

方法：从倒数第一个非叶子结点（最后一个结点的父亲）开始调整 最后调整到根节点

二、手动建堆时间复杂度对比分析

1.向上调整建堆时间复杂度O(N*logN)

2.向下调整建堆时间复杂度O(N)