【从零开始学数据结构 ⑥】：二叉树之堆——打破规则的优先队列
文章目录
[一. 引言](#一. 引言)
[二. 核心概念：逻辑树与物理数组的映射](#二. 核心概念：逻辑树与物理数组的映射)
1）二叉树的存储结构
[三. 方案的选择：普通数组 vs 堆](#三. 方案的选择：普通数组 vs 堆)
[四. 核心功能的逻辑实现](#四. 核心功能的逻辑实现)
[1. 堆的结构体定义与物理架构](#1. 堆的结构体定义与物理架构)
[2. 标准初始化与资源销毁](#2. 标准初始化与资源销毁)
[3. 稳健入堆：动态扩容与向上调整](#3. 稳健入堆：动态扩容与向上调整)
1）向上调整法
2）思考
[4. 精准出堆：堆顶删除与向下调整](#4. 精准出堆：堆顶删除与向下调整)
向下调整法
[5. 堆顶获取与判空](#5. 堆顶获取与判空)
1）获堆顶
2）判空
[五. 进阶应用与延伸](#五. 进阶应用与延伸)
1）原地建堆
[1. 向上调整法原地建堆 ( O(N * log N) )](#1. 向上调整法原地建堆 ( O(N * log N) ))
[2. 向下调整法原地建堆 ( O(log N) )](#2. 向下调整法原地建堆 ( O(log N) ))
2）TopK问题
一.引言
在上一篇文章中，我们讲到了队列 ，队列讲究的是绝对的公平 ，遵循 FIFO（First In, First Out，先进先出）线性原则，
堆 打破了纯粹的时间顺序，出队时不看是谁先来的，而是看"谁的优先级高/谁的数据最大（或最小）"。
生动比喻：
像是在车站排队买票，先来后到；而堆就像是医院的急诊室，病情最严重的患者（优先级最高）哪怕最后进来，也会被优先安排治疗。
二.核心概念：逻辑树与物理数组的映射
堆本质是由完全二叉树构成，如图
在这里我们可以发现树的构成，是由众多个节点所连接而成，那么我们联系之前所学知识可以想到，这种树的连接方式用链表最合适不过了，毕竟从图中就可以发现他是相互连接起来的，在这里我们就要讲二叉树的两种存储结构。
1）二叉树的存储结构
顺序存储 （顺序结构）
顺序存储就是利用数组 来进行数据存储，只适合完全二叉树，即每个父节点都会有两个子节点（我们所学的堆即是顺序存储）
完全二叉树
非完全二叉树
- 链式存储（链式结构）
顾名思义，如同链子般，即利用链表进行连接，通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
所以我们在利用顺序结构创建堆时，实际上是在控制数组的变化
三.方案的选择：普通数组 vs 堆
如果要实时维护一组数据的最大值/最小值，普通无序数组和有序数组有什么缺陷？
无序数组：普通无序数组插入数据快，但是每次获取或者删除数据需要全盘遍历 O(N)。
有序数组：取最大或最小值极快（头和尾）， 但是插入或删除数据时，需要移动大量元素来维护顺序 O(N)。
堆（大堆/小堆） ：两头兼顾，高效平衡，找极值直接看堆顶 O(1)；无论插入还是删除数据，只需要向上向下调整 O(log N) 即可恢复堆性质。
四.核心功能的逻辑实现
1. 堆的结构体定义与物理架构
为更好的控制堆，我们将数组等定义在一个结构体中，类似于顺序表的形式
c
复制代码
typedef int TypeData; // 将类型重命名
typedef struct Heap
{
TypeData* a; // 定义数组
int size; // 有效个数
int capacity; // 空间容量
} Hp;
# 一.引言
在上一篇文章中，我们讲到了**队列**，队列讲究的是**绝对的公平**，遵循 FIFO（First In, First Out，先进先出）线性原则，
**堆**打破了存粹的时间顺序，出队时不看是谁先来的，而是看"**谁的优先级高/谁的数据最大（或最小）**"。
**生动比喻：**
像是在车站排队买票，先来后到；而堆就像是医院的急诊室，病情最严重的患者（优先级最高）哪怕最后进来，也会被优先安排治疗。
# 二.核心概念：逻辑树与物理数组的映射
堆本质是由完全二叉树构成，如图
在这里我们可以发现树的构成，是由众多个节点所连接而成，那么我们联系之前所学知识可以想到，这种树的连接方式用链表最合适不过了，毕竟从图中就可以发现他是相互连接起来的，在这里我们就要讲二叉树的两种存储结构。
## 1）二叉树的存储结构
- 顺序存储 （顺序结构）
顺序存储就是利用**数组**来进行数据存储，只适合完全二叉树，即每个父节点都会有两个子节点（我们所学的堆即是顺序存储）
**完全二叉树**
**非完全二叉树**
**- 链式存储（链式结构）**
顾名思义，如同链子般，即利用链表进行连接，通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所
在的链结点的存储地址 。
**所以我们在利用顺序结构创建堆时，实际上实在控制数组的变化**
# 三.方案的选择：普通数组 vs 堆
如果要实时维护一组数据的最大值/最小值，普通无序数组和有序数组有什么缺陷？
- **无序数组**：普通无序数组插入数据快，但是每次获取或者删除数据需要全盘遍历O(1)。
- **有序数组**：取最大或最小值极快（头和尾）， 但是插入或删除数据时，需要移动大量元素来维护顺序 O(N)。
- **堆（大堆/小堆）**：**两头兼顾，高效平衡**，找极值直接看堆顶O(1)；无论插入还是删除数据，只需要向上向下调整 O(Log N) 即可恢复堆性质。
# 四.核心功能的逻辑实现
## 1. 堆的结构体定义与物理架构
为更好的控制堆，我们将数组等定义在一个结构体中，类似于顺序表的形式
```c
typedef int TypeData;//将类型重命名
typedef struct Heap
{
TypeData* a;//定义数组
int size;//有效个数
int capacity;//空间容量
}Hp;
2. 标准初始化与资源销毁
c
复制代码
//初始化
void HpInit(Hp* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
//销毁
void HpDeatroy(Hp* php)
{
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
这里释放掉数组后，记得置空，防止野指针出现
3. 稳健入堆：动态扩容与向上调整
入堆的前提是，堆内空间充足，所以我们需要先判断是否空间充足，再进行入堆操作
c
复制代码
void IsFull(Hp* php)
{
//插入前先判断空间是否充足
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
TypeData* tmp = (TypeData*)realloc(php->a, newcapacity * sizeof(TypeData));
//判断是否扩容成功
if (tmp == NULL)
{
return;
}
php->capacity = newcapacity;
php->a = tmp;
}
}
这里我们复习一个操作符，"三目操作符" -------条件 ？1 ：2
？前的条件如果为真则执行1操作，？前的条件若为假则执行2
有了以上扩容的知识，我们就可以进行接下来的入堆操作了
c
复制代码
//入堆
void HpPush(Hp* php, int x)
{
assert(php);
//插入前先判断空间是否充足
IsFull(php);
//插入数据
php->a[php->size] = x;
php->size++;
//插入后向上调整算法，调整堆内元素顺序
AdjustUp(php->a, php->size - 1);
}
1）向上调整法
原理：新元素"入堆"放在末尾，逐层向上与父节点比较并交换（从下往上"浮"）。
适用场景：HpPush 插入元素、向上调整建堆。
因为堆分为大堆和小堆，那么堆便具有一定的大小关系，所以为了插入数据后还能够维持相互的大小关系，那么就要用到向上调整法
我们先看例子
不难看出这是一个大堆，我们假若要再插入一个数字9 ，那么它的调整图是什么样子的呢
因为我们是大堆，在填加一个数据时，是添加到了数组最后一个，所以如果它的值很大则需要与上面的父节点进行交换
c
复制代码
//向上调整算法
//交换
void Swap(TypeData* p1, TypeData* p2)
{
TypeData tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(TypeData* a, int child)//注意这里穿得是下标
{
//假设建大堆
assert(a);
while (child > 0)
{
int parent = (child - 1) / 2;
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
}
else
{
break;
}
}
}
遇到有子比父大的元素时，则交换数据，并且更新下标，再次进行对比交换，直到结束
注意循环条件不能等于0， 因为0节点无任何父节点。
我们随便创造一个数组测试一下，看功能是否正常。
c
复制代码
void Heaptest01()
{
Hp hp;
HpInit(&hp);
TypeData arr[] = {1, 5, 6,4,3,8,7,9,12};
for (int i = 0; i < sizeof(arr) / sizeof(TypeData) ; i++)
{
//入堆
HpPush(&hp, arr[i]);
}
HpDeatroy(&hp);
}
由监视得到我们的HpPush功能正常。
2）思考
为什么在向上调整法时传参不直接传入结构体指针呢？而是传入数组呢？
4. 精准出堆：堆顶删除与向下调整
想象一下，在一个堆中，我们要删除堆顶数据，如果直接删除再将数组内元素依次覆盖，可以吗？
答案是不行，如果直接覆盖，那么顺序将会被打乱，无法维持堆性质，通俗点说，亲属关系则会混乱。
那么我们该如何解决这个问题呢？
c
复制代码
//删除
void HpPop(Hp* php)
{
assert(php);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
//向下调整算法
AdjustDown(php->a, 0, php->size);
}
向下调整法
原理：堆顶元素被替换后，从根节点开始逐层向下与左右孩子中的较优者比较并交换（从上往下"沉"）。
适用场景：HpPop 删除堆顶、向下调整建堆。
通过头尾交换 ，在保证不破环堆性质的前提下，将堆顶数据删除（即 size--），在对堆顶元素进行向下调整，将父节点与较大的子节点进行比较互换，然后更新下标，将换下去的子节点继续与其子节点进行比较互换。
c
复制代码
//向下调整算法
void AdjustDown(TypeData* a, int parent, int n)
{
assert(a);
int child = parent * 2 + 1;
while (child < n)
{
//假设法建大堆
if (child + 1 < n && a[child] < a[child + 1])
{
++child;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
细节避坑： 向下调整时右孩子越界的边界条件处理（如 child + 1 < n）。child满足界限child + 1不一定满足界限。
child满足child < n - 1,所以child + 1满足child + 1 < n;
我们继上一次的代码，继续测试一下删除功能是否正常。
c
复制代码
void Heaptest01()
{
Hp hp;
HpInit(&hp);
TypeData arr[] = {1, 5, 6,4,3,8,7,9,12};
for (int i = 0; i < sizeof(arr) / sizeof(TypeData) ; i++)
{
HpPush(&hp, arr[i]);
}
//出堆
HpPop(&hp);
HpDeatroy(&hp);
}
正常。
5.堆顶获取与判空
堆顶获取即直接返回数组首元素即可
1）获堆顶
c
复制代码
TypeData HpTop(Hp* php)
{
assert(php);
return php->a[0];
}
2）判空
错误示范：
c
复制代码
bool HpEmpty(Hp* php)
{
assert(php);
if (php->a == NULL)
{
return true;
}
else
{
return false;
}
}
思考： 为什么这样不可以？
数组为空确实是一种为空情况，但是如果当数组内数据被HpPop函数删除完，虽然数组内已经没有了元素，但是它也不指向空，所以这种判断方法并不严谨。所以只需要根据数组内元素个数是否为零来判断是否为空即可。
c
复制代码
bool HpEmpty(Hp* php)
{
assert(php);
return php->size == 0;
}
五.进阶应用与延伸
1）原地建堆
1.向上调整法原地建堆 （ O(N * log N) )
假设给定我们一个数组，我们想将数组变成堆的形式，那么按照以前的方法只需要通过HpPush函数依次入堆即可，但是这样我们需要另外开辟一个空间来存储，有没有办法不另外开辟空间来进行堆的构造呢？
c
复制代码
void Heaptest02()
{
//原地建堆
TypeData arr[] = { 1, 5, 6, 4, 3, 8, 7, 9, 12 };
//若使用HpPush进行建堆，则需要另外开辟空间，而原地建堆则无需开辟额外空间
for (int i = 1; i < sizeof(arr) / sizeof(TypeData); i++)
{
AdjustUp(arr, i);
}
}
我们将第一个元素看成堆，从第二个元素开始向上调整，调整完向后移动一个数据单位，再次进行向上调整，从此达到原地调整，即原地建堆
2.向下调整法原地建堆（ O（logN) )
何为向下调整建堆呢？也是在给定数组中进行数据的交换，以此满足堆的性质。
我们先给一个数组，画出他的堆示意图
向下调整原地建堆，第一个操作对象是最后一个非叶子节点，将整个堆分解成众多个堆，依次进行从小往大的思想进行调整，"先局部，后整体"
先从最小单位，最后一个叶子节点开始调整，假设我们要键大堆，那么节点 3 与 节点1和4中较大的比较交换
c
复制代码
void Heaptest03()
{
//向下调整原地建堆
TypeData arr[] = { 2, 9, 5, 3, 7, 6, 4, 1, 4 };
int leaf = (sizeof(arr) / sizeof(TypeData) - 2) / 2;
for (int i = leaf; i >= 0; i--)
{
AdjustDown(arr, i, sizeof(arr) / sizeof(TypeData));
}
}
2）TopK问题
假设给了我们一个文件，文件中有众多数据，让我们找出前K个最大的值，我们该怎么办呢？
首先想到的就是将这些数组全部Push到堆中去，然后依次首尾交换Pop出来，但是这样假如数据量非常大，我们堆所开辟的空间是非常之大的，如果限定内存空间，我们需要怎么做呢？
假如只给了我们1kb，全量Push是肯定不可以的，那么这时候我们就需要取前K个值建立一个小堆，然后依次往后读取数据，读取到的数据与堆顶元素进行对比，如果比堆顶小则继续读取，如果比堆顶大那么就取代堆顶元素并进行向下调整，直到读取完整个文件内数据，此时堆内元素则是所有元素中最大或者最小的元素。