堆
1. 什么是堆
在树和二叉树一文中可以了解到：
堆通常是一个可以被看作一棵完全二叉树的数组对象。
- 堆的逻辑结构是一棵完全二叉树
- 堆的物理结构是一个数组
如图所示：
2. 堆的两个特性
- 结构性：用数组表示的完全二叉树
- 有序性：任意节点的关键值是其子树所有节点的最大值（或最小值）
- ”最大堆(MaxHeap)“，也叫”大顶堆“：最大值，即每棵子树的根节点的值都大于等于其子节点的值
- ”最小堆(MaxHeap)“，也叫”小顶堆“：最小值，即每棵子树的根节点的值都小于等于其子节点的值
我们通过一道例题来加深对堆的理解：
下列关键字序列中，序列 () 是堆
A.(16，72，31，23，94，53)
B.(94，23，31，72，16，53)
C.(16，53，23，94，31，72）
D.(16，23，53，31，94，72)
我们可以通过画图来分析：
通过分析我们可以知道，只有序列D符合堆的条件，其每个子树的父亲都小于它的孩子，因此这也是一个小堆。
3. 父子节点下标之间的关系
我们定义父亲为parent，左右孩子为leftchild, rightchild
- 我们可以通过数组的下标来确定父子节点的关系，结论如下
leftchild = parent * 2 + 1
rightchild = parent * 2 + 2
parent = (child - 1) / 2
4. 堆的实现
由于堆的物理存储结构是一个数组，因此我们可以像定义顺序表一样定义堆的结构：
typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; //记录当前数据个数 int capacity; //记录最大容量 }Heap;
4.1 堆的插入HeapPush
向堆中插入数据，在内存中也就相当于向一个数组插入数据，而为了确保效率，显然我们应该将新数据val插入到数组尾部。
如图所示：
此时我们发现，数据10插入后，这一串数据构成的完全二叉树就不满足堆的性质了。因此为了确保堆结构的正确性，每插入一次数据，我们都要重新对堆进行调整
4.1.1 向上调整算法AdjustUp：
调整的整体原则是：
- 如果原来是小堆，并且插入的数据
val小于父亲parent，那么就将val和parent调换位置。继续向根部向上调整，直到满足所有的父亲小于等于它的孩子。- 大堆同理。
例如：
4.1.2 AdjustUp代码实现（以大堆为例）
void AdjustUp(HPDataType* a, int child) { //新插入数据的父亲 int parent = (child - 1) / 2; //开始向上调整 while (child > 0) { //如果孩子大于父亲，那就要交换 //并继续向上调整 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (parent - 1) / 2; } //否则说明已经符合堆的性质，退出循环 else break; } }
4.1.3 HeapPush实现
知道了如何向上调整，那么堆的插入就很简单了。只需要在插入新的数据后进行一次向上调整就行。
void HeapPush(Heap* hp, HPDataType x) { //检查容量 if (hp->size == hp->capacity) { hp->capacity *= 2; HPDataType* temp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * hp->capacity); if (NULL == temp) { perror("realloc"); exit(-1); } } hp->a[hp->size] = x; hp->size++; AdjustUp(hp->a, hp->size - 1); }
4.1.4 时间复杂度
对于每一次插入，向上调整时最多调整二叉树的高度次，假设二叉树有N个节点，那么它的高度h就是log2(N+1)，即时间复杂度为O(logN)
4.2 堆的删除HeapPop
首先我们应该思考，对于构成堆的数组，我们应该删除数组的第一个元素还是最后一个元素？
可能有的小伙伴觉得为了使删除的效率最高，应该删除数组的最后一个元素，但是这种做法是没有任何意义的。
应该清楚，堆顶元素(即数组的首元素)要么是整个数组的最大值，要么是整个数组的最小值，因此对这一个数进行操作才能有较大的意义
正确的删除操作HeapPop应该是这样的：
- 删除的数据应该是堆顶元素
- 将堆顶元素（即数组首元素）和数组最后一个元素调换位置
- 再删除最后一个元素
如图：
显然我们可以看到，和插入操作一样，删除操作后仍不能保证堆结构的正确性，因此我们仍需要重新对堆进行调整
4.2.1 向下调整算法AdjustDown
删除操作中我们将原来数组的最后一个元素放到了堆顶，从而导致堆顶数据不一定满足堆的条件，因此我们也要从堆顶开始向下调整。
调整的整体原则是：
如果原来是小堆：将堆顶数据和左右孩子较小的那一个比较，如果堆顶数据大于较小值，那么就交换这两个数的位置。继续向下调整，直到满足堆的条件
大堆同理。
如图：
4.2.2 AdjustDown实现（大堆）
void AdjustDown(HPDataType* a, int parent, int n) { //先默认较大的孩子为左孩子 int child = parent * 2 + 1; while (child < n) { //如果右孩子存在并且右孩子大于左孩子 //那么较大的孩子应该是右孩子 if (child + 1 < n && a[child + 1] > a[child]) child = child + 1; //如果父亲小于孩子，那就交换父亲和孩子 //并继续向下调整 if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); parent = child; child = child * 2 + 1; } //否则已经满足堆的条件，退出循环 else break; } }
4.2.3 HeapPop实现
和插入类似，只要每删除一次数据就进行一次向下调整，就可以保证HeapPop的正确了：
void HeapPop(Heap* hp) { //交换堆顶元素和数组最后一个元素 Swap(&(hp->a[0]), &(hp->a[hp->size - 1])); //更新大小 hp->size--; //向下调整 AdjustDown(hp->a, 0, hp->size); }
4.2.4 时间复杂度
和向上调整一样，对于每一次删除，向下调整最多调整高度次，因此时间复杂度为O(logN)
4.3 堆的构建
应该清楚，执行堆的插入和删除之前，堆已经被建立。换一句话说，如果任意给一组数据，同时要对其进行堆的插入删除操作，首先就要确保这一组数据是堆。因此掌握如何建堆是十分重要的。
有两种方式建堆：
4.3.1 向上调整建堆
实现堆的插入时，我们用向上调整的方式来建堆。同样，对于任意一个给定的数组，我们也可以用类似“插入”的方法来建堆。
具体方法（以建大堆为例）：
- 遍历数组
- 数组首元素可以默认为一个大堆
- 从第二个元素开始遍历，可以看作每遍历一个数据，就将这个数据
HeapPush到堆中- 直到遍历完整个数组
for (int i = 1; i < n; i++) AdjustUp(hp->a, i);
- 时间复杂度：O(NlogN)
4.3.2 向下调整建堆
也可以采用分治的思想：如果构成二叉树的所有子树都是堆，那么这棵二叉树也就一定是堆。
那么我们就可以从最后一棵子树开始，用向下调整的方法建堆：
具体方法：
- 最后一个元素的下标为
size - 1，其对应父亲parent的下标为(size - 1 - 1)/2- 从
parent开始向前遍历数组，对每一棵子树进行向下调整- 直到遍历完整个数组
int parent = (hp->size - 1 - 1) / 2; while (parent >= 0) { AdjustDown(hp->a, parent, hp->size); parent--; }
- 时间复杂度：O(N)
5. 堆的应用
堆的主要用途有堆排序和处理TopK问题，感兴趣的小伙伴可以点击下面的链接进行进一步了解：
👉堆排序
