文章目录
一、堆的概述
1. 堆的概念
2. 堆的性质
3. 堆的结构
3.1 小根堆
3.2 大根堆
4. 堆与栈的区别
5. 堆的存储
二、堆的基本操作具体实现见例题模拟堆
1. 下滤
2. 上滤
3. 建堆
3.1 自上向下建堆法
3.2 自下而上建堆法
4. 堆的插入
5. 堆的删除
三、堆的应用
1. 优先队列
2. 堆排序具体实现见例题堆排序
2.1 堆排序概念
2.2 堆排序步骤图解——构造
2.3 堆排序步骤图解——排序
四、堆例题——堆排序
具体实现
1. 实现思路
2. 代码注解
3. 实现代码
五、堆例题——模拟堆
具体实现
1. 代码注解
2. 实现代码
STL 中关于堆的操作会在后续会补充。
一、堆的概述
1. 堆的概念
- 堆是计算机科学中一类特殊的数据结构的统称，是一个完全二叉树。
- 完全二叉树只允许最后一行不为满，且最后一行必须从左往右排序，最后一行元素之间不可以有间隔，具体如下图所示：
如果有一个关键码的集合 K = { k0，k1， k2，…，kn-1 } ，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，我们可以发现若父节点下标是 i ，则他的左子节点下标是 2i + 1 ，右子节点下标是 2i + 2。
由小堆（大堆）的名字我们可以发现，如果一个堆满足：Ki <=（或>=） K2i+1 且 Ki <=（或>=） K2i+2 ，则称为小堆(大堆)。
将根节点最大的堆叫做最大堆或大根堆。
将根节点最小的堆叫做最小堆或小根堆。
2. 堆的性质
- （1） 堆序性：堆中某个结点的值总是不大于或不小于其父结点的值。
- （2） 堆总是一棵完全二叉树。
3. 堆的结构
3.1 小根堆
小根堆是根节点最小的堆
3.2 大根堆
- 大根堆是根节点最大的堆。
4. 堆与栈的区别
（1） 申请方式的不同。栈由系统自动分配；而堆是人为申请开辟。
（2） 申请大小的不同。栈获得的空间较小；而堆获得的空间较大。
（3） 申请效率的不同。栈由系统自动分配，速度较快；而堆一般速度比较慢。
（4） 存储内容的不同。栈在函数调用时，函数调用语句的下一条可执行语句的地址第一个进栈，然后函数的各个参数进栈，其中静态变量是不入栈的；而堆一般是在头部用一个字节存放堆的大小，堆中的具体内容是人为安排。
（5） 底层不同。栈是连续的空间；而堆是不连续的空间。
5. 堆的存储
- 首先，我们按照层序遍历的顺序来给结点编号，一般是从上到下，从左到右，把这些编号对应到数组的下标，然后把树的元素存入相应的下标里。
- 因为堆是完全二叉树，所以每个下标和树的每个位置是一 一对应的，这样一个堆就可以用一个一维数组来存储。
二、堆的基本操作具体实现见例题模拟堆
1. 下滤
这是一个只有根节点元素不满足堆序性的树。主要考虑 2i 和 2i+1 和 i 的关系。
这里以大根堆为例：
将破坏堆序性的元素跟他最大的子节点进行比较。
如果小于他的最大子节点，则与之交换，持续比较、交换，直到该元素大于他的子节点为止（或者移动到底部为止）。
此时，该树就成功地被调整为一个大根堆，满足了堆序性。
2. 上滤
- 这是一个只有最后一个元素不满足堆序性的树。主要考虑 p/2 和 p 的关系
- 与下滤同理，让他和他的父元素进行比较， 若大于父节点则交换，直到无法上移为止。
- 这个操作主要用于插入新元素的堆中。
3. 建堆
- 如果有一个乱序的数组，可以通过自上向下和自下而上两种方法进行建堆。
3.1 自上向下建堆法
- 假设有一个数组 = [3，4，5，6，1，7，8]。
- 我们先将元素一个一个插入堆内，将新元素放到堆的最后一位，然后对其进行上滤操作。
- 直到所有元素插入后完成建堆。
3.2 自下而上建堆法
- 假设有一个数组 = [3，4，5，6，1，7，8]。
- 先把下面的元素调整成堆，然后再对父节点进行下滤操作。
- 具体是从倒数第二排开始，对每一个父节点进行下滤操作，直到根节点，操作完毕
4. 堆的插入
- 就是上滤操作的应用，将数据插入到数组最后，再进行向上调整。
5. 堆的删除
- 删除堆是删除堆顶的数据。
- 将堆顶的数据和最后一个数据交换，然后删除数组最后一个数据，再进行下滤。
三、堆的应用
1. 优先队列
- 优先队列有两个操作，一个是插入队列，另一个是弹出最小元素。
- 这种队列可以用小根堆进行实现，因为小根堆的根节点本来就是最小元素，所以直接弹出根节点就可以完成弹出操作。
- 弹出后将剩下的元素调整成堆，可以通过将最后一个元素放到根节点，然后进行下滤操作。
2. 堆排序具体实现见例题堆排序
2.1 堆排序概念
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序， 它的最坏、最好、平均时间复杂度均为 O(NlogN)， 它也是不稳定排序。
- 用大根堆排序得到的是升序的，用小根堆排序得到的是降序的。
- 将待排序序列构造成一个大根堆。
- 此时，整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换， 此时末尾就为最大值。
- 然后将剩余 n-1 个元素重新构造成一个大根堆， 这样会得到 n 个元素的次小值。 如此反复执行， 便能得到一个有序序列了。
2.2 堆排序步骤图解——构造
- 数组 [4，6，8，5，9] 要求使用堆排序法，将数组升序排序。
- （1） 将给定无序序列结构构造如下。
（2） 从最后一个非叶子节点开始，从右至左，从下至上进行调整。
调整规则：找到该节点和他的所有子节点。如果该节点中存的值是找到节点值中的最大值，则不进行调整。如果不是，就将该节点的值和最大值进行交换，然后递归的调整和该节点交换值得那个节点。如下图：
最后一个非叶子节点开始（也就是下面的 6 节点），从左至右，从下至上进行调整。6 有两个子节点：5 和 9，这三个值中 9 最大。6 和 9 交换。
- 因为 6 和 9 交换了，递归处理现在保存 6 的那个节点，发现它没有子节点，停止递归。
- 找到第二个非叶子节点 4，由于 [4, 9, 8] 中 9 元素最大，4 和 9 交换。
因为 4 和 9 交换了，递归处理现在保存 4 的那个节点: 找到它的两个子节点：5 和 6, 其中 6 最大，交换 4 和 6。
然后继续递归处理，发现现在保存4 的节点没有儿子，停止。
此时，我们就将一个无序序列构造成了一个大根堆。
2.3 堆排序步骤图解——排序
将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。如下图：
重新调整结构（规则如上），使其继续满足堆定义。
- 再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8。
- 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。
