前言
堆分为两种，一种是大堆（大根堆），还有一种是小堆（小根堆）。本篇文章将会通过实现大堆的方式来让大家理解堆方面的知识。小堆可根据大堆稍做修改即可。
文章末尾附带源码。
一、堆的概念及结构
堆是一种特殊的数据结构，本质上是一种完全二叉树。堆的特点是，如果是小堆，那么所有的父结点都要比其子结点要小，大堆则相反，所有的父结点都要比其子结点要大。由此可知，大堆的根结点肯定是整个堆的最大值，小堆的根结点肯定是整个堆的最小值。
堆在逻辑结构上是一颗完全二叉树。堆在物理结构上是一个数组。
其中很容易看出，每个父结点都是比其子结点要大，根结点也是堆中的最大值。
二、头文件的编写
我们创建一个头文件，叫做 “Heap.h” 。
1.引入库函数头文件
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h>
2.定义堆结构体
// 宏定义数据类型 typedef int HPDataType; // 堆结构体 typedef struct Heap { // 指向数组的指针，数组的元素类型为HPDataType HPDataType* a; // 数组、堆的有效元素个数 int size; // 数组的容量 int capacity; }HP;
在一般情况下，堆都是存放的都是 int 类型的数据，所以其实也可以不用 typedef 来宏定义数据类型。堆一般都是采用顺序表的结构来存储的，所以我们在创建堆结构体的时候，模仿顺序表的结构体就可以了。
3.声明功能函数
// 堆的初始化 void HeapInit(HP* php); // 销毁 void HeapDestroy(HP* php); // 往堆中插入数据 void HeapPush(HP* php, HPDataType x); // 删除堆顶元素 void HeapPop(HP* php); // 查询堆顶元素 HPDataType HeapTop(HP* php); // 查询堆的有效数据个数 int HeapSize(HP* php); // 判断堆是否为空，为空则真 bool HeapEmpty(HP* php);
三、 主函数文件的编写
我们创建一个源文件，叫做 “test.c” 。
1.包含头文件
#include"Heap.h"
2.编写测试用例
void Test01() { // 创建一个无序集合 int arr[] = { 245,7345,123,874,43,78,235,6457,1235,784,34,63,2 }; // 创建一个堆 HP hp; // 将堆初始化 HeapInit(&hp); // 将集合中的元素挨个插入到堆里面 for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) { HeapPush(&hp, arr[i]); } // 如果堆不为空 while (!HeapEmpty(&hp)) { // 打印堆顶元素 printf("%d ", HeapTop(&hp)); // 删除堆顶元素 HeapPop(&hp); } printf("\n"); // 销毁堆 HeapDestroy(&hp); }
3.主函数的编写
int main() { // 调用测试用例 Test01(); // 程序正常结束 return 0; }
四、功能函数的编写
我们创建一个源文件，叫做 “Heap.c” 。
1.包含头文件
#include"Heap.h"
2.堆的初始化
void HeapInit(HP* php) { // php为指向堆结构体的指针，不管堆里是否有元素，堆结构体都存在，所以该指针不可能为空，可以断言一下 assert(php); // 指向数组的指针初始化为不指向任何空间 php->a = NULL; // 堆的有效数据个数为0个 php->size = 0; // 数组的容量为0 php->capacity = 0; }
对于堆的初始化，我们将堆初始化为不包含任何元素。并且存储元素的空间也没有被开辟。我们采用动态分配空间的方式存储堆的元素，以避免空间的浪费，所以在初始化的时候，容量可以被赋值为0。
3.堆的销毁
void HeapDestroy(HP* php) { // php不可能为空，值得断言一下 assert(php); // 释放数组空间 free(php->a); // 释放空间后，指针需要置空 php->a = NULL; // 堆的有效数据变为0 php->size = 0; // 数组的容量变为0 php->capacity = 0; }
由于堆是由顺序表实现的，所有的数据都存放在一个数组里面，我们可以直接通过释放数组的空间来销毁所有的数据，同时将堆结构体的值重置为初始化状态即可。
4.往堆里面插入数据
void HeapPush(HP* php, HPDataType x) { // php不可能为空 assert(php); // 扩容情况，如果堆的有效数据个数与容量相同 if (php->size == php->capacity) { // 通过三目运算符来建立新的容量 int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity; // 通过新的容量开辟新的空间大小，让临时指针指向新空间 HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity); // 如果开辟空间失败 if (tmp == NULL) { // 弹出反馈 perror("realloc fail"); // 终止程序 exit(-1); } // 使指向数组的指针指向新的数组空间 php->a = tmp; // 将进度容量赋值给旧的容量 php->capacity = newcapacity; } // 将待插入的值插入到堆的末尾 php->a[php->size] = x; // 堆的有效数据个数+1 ++php->size; // 数据插入到堆的末尾后需要将其调整位置，令新数据移动到其正确的位置 AdjustUp(php->a, php->size - 1); }
在向堆中插入数据时，第一件事就是需要判断堆是否已经满了，堆满了自然是不能插入，需要进行扩容操作。我们堆是使用顺序表实现的，顺序表非常擅长在尾部插入删除，所以我们插入数据的时候，直接插入到堆的末尾即可，但是，插入到末尾就结束了吗，那肯定不是，该数据有很大可能不应该在这个位置，而在堆的其他位置，所以我们需要调整这个元素的位置。于是我们创建了一个 AdjustUp 函数来实现调整。
5.将堆的末尾元素向上调整到正确位置
// 参数为指向数组的指针和待调整元素的下标 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 = (child - 1) / 2; } // 如果父结点的值已经比子结点要大，说明待调整位置的元素已经到了其应该到的位置 else { // 说明堆已经是新的小堆了，可以直接结束循环 break; } } }
在插入新数据后，由于新数据可能不应该在那个位置，所以需要进行调整。大堆的定义就是所有的父结点都比其子结点要大，所以插入的数据不断的跟其祖先进行比较，如果比父结点大，则跟父结点的值进行交换，如果比父结点小，说明新数据到了其应该到的位置，结束调整即可。
6.交换函数
// 由于交换的是两个堆的元素，所以参数是两个指向堆元素的指针 void Swap(HPDataType* p1, HPDataType* p2) { // 创建临时变量赋值为p1指向的空间的数据 HPDataType tmp = *p1; // 将p2指向的空间的数据赋值给p1指向的空间的数据 *p1 = *p2; // 将原p1指向的空间的数据赋值给p2指向的空间的数据 *p2 = tmp; }
交换函数不多说，要注意的是，形参只是实参的一份临时拷贝，改变形参的值是不能改变实参的值的，所以需要通过指针的方式来间接改变两个数据的值。
7.删除堆顶的元素
void HeapPop(HP* php) { // php不能为空 assert(php); // 堆必须有数据才能删除 assert(php->size > 0); // 交换堆顶元素和堆末尾的元素的数据 Swap(&php->a[0], &php->a[php->size - 1]); // 使堆的有效数据-1 --php->size; // 将原堆末尾的元素移到堆顶后需要进行调整位置，使其移动到其应该在的位置 AdjustDown(php->a, php->size); }
堆的删除就是删除堆顶元素，因为堆只有堆顶元素是最特殊的，在大堆中，堆顶元素就是堆的最大值，在小堆中，堆顶元素就是堆的最小值。我们删除的时候当然不能直接删除第一个元素，因为这样操作会打乱堆的结构。最有效的方法就是，将堆顶元素与堆的最后一个元素进行交换，然后直接令堆的有效数据 -1 即可。此时，堆顶元素变成了原来的堆的末尾的元素，位置是肯定不符合的，于是我们最后将其与其孩子进行比较，向下调整即可。
8.将堆顶元素向下调整到正确位置
// 向下调整函数需要的参数有指向数组的指针和堆的有效数据个数 void AdjustDown(HPDataType* a, int size) { // 待调整元素为堆顶元素，下标为0 int parent = 0; // 待调整元素的左孩子的下标 int child = parent * 2 + 1; // 待调整元素的左孩子的下标必须是堆的有效数据下标内，否则孩子不存在 while (child < size) { // 当右孩子存在并且右孩子比左孩子要大时 if (child + 1 < size && a[child] < a[child + 1])// 小堆则修改第二个 < 为 > { // 找出左右孩子中最大值 ++child; } // 如果最大的孩子要比父结点大，说明该孩子更应该做父结点，应该与待调整元素进行交换 if (a[parent] < a[child]) { // 交换待调整元素与孩子的值 Swap(&a[parent], &a[child]); // 原孩子下标成为新的待调整元素的下标 parent = child; // 找到新的左孩子下标 child = parent * 2 + 1; } // 如果最大的孩子没有父结点大，说明待调整元素以及到了其应该在的位置 else { // 跳出循环，结束调整 break; } } }
在将堆的末尾元素交换到堆顶后，堆的结构发生了改变，我们需要将堆顶元素进行调整，使其回到其应该在的位置，让堆的结构恢复。在待调整元素向下调整中，待调整元素需要不断与其最大的孩子进行比较，找出三者中的最大值，最大值才能作为新的父结点。当待调整元素以及比其两个孩子都要大时，说明待调整元素以及到了其应该在的位置，堆的结构以及恢复，可以结束调整。
9.查询堆顶元素数据
// 返回类型是堆存储的数据类型 HPDataType HeapTop(HP* php) { // php不可能为空 assert(php); // 当堆中有数据时才能查看堆顶元素数据 assert(php->size > 0); // 返回数组下标为0的数据 return php->a[0]; }
堆的元素是以数组的方式存储的，且堆顶元素就是数组的首元素，所以返回数组首元素的数据即可。
10.查询堆的有效数据个数
int HeapSize(HP* php) { // php不可能为空，值得断言一下 assert(php); // 返回size的值 return php->size; }
由于 size 的值就是堆的有效数据个数，所以我们直接将其返回即可。
11.判断堆是否为空
bool HeapEmpty(HP* php) { // php不可能为空 assert(php); // 如果堆的有效数据个数为0，说明堆为空，返回真，否则返回假 return php->size == 0; }
当堆中无有效数据个数时，size的值肯定为0，否则不为0，可以借此来判断堆是否为空。
五、代码整合及结果演示
1.代码整合
若是在整合后出现某些函数不安全的错误，请在头文件里面加上下面这行代码。
#define _CRT_SECURE_NO_WARNINGS 1
1.头文件 Heap.h 部分
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; void HeapInit(HP* php); void HeapDestroy(HP* php); void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); HPDataType HeapTop(HP* php); int HeapSize(HP* php); bool HeapEmpty(HP* php);
2.源文件 Heap.c 部分
#include"Heap.h" void HeapInit(HP* php) { assert(php); php->a = NULL; php->size = 0; php->capacity = 0; } void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = 0; php->capacity = 0; } void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } 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 = (child - 1) / 2; } else { break; } } } void HeapPush(HP* php, HPDataType x) { assert(php); if (php->size == php->capacity) { int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } php->a = tmp; php->capacity = newcapacity; } php->a[php->size] = x; ++php->size; AdjustUp(php->a, php->size - 1); } void AdjustDown(HPDataType* a, int size) { int parent = 0; int child = parent * 2 + 1; while (child < size) { if (child + 1 < size && a[child] < a[child + 1]) { ++child; } if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapPop(HP* php) { assert(php); assert(php->size > 0); Swap(&php->a[0], &php->a[php->size - 1]); --php->size; AdjustDown(php->a, php->size); } HPDataType HeapTop(HP* php) { assert(php); assert(php->size > 0); return php->a[0]; } int HeapSize(HP* php) { assert(php); return php->size; } bool HeapEmpty(HP* php) { assert(php); return php->size == 0; }
3.源文件 test.c 部分
#include"Heap.h" void Test01() { int arr[] = { 245,7345,123,874,43,78,235,6457,1235,784,34,63,2 }; HP hp; HeapInit(&hp); for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) { HeapPush(&hp, arr[i]); } while (!HeapEmpty(&hp)) { printf("%d ", HeapTop(&hp)); HeapPop(&hp); } printf("\n"); HeapDestroy(&hp); } int main() { Test01(); return 0; }
2.结果演示
1.创建的堆的结构
符合大堆的结构。
2.依次取出的堆顶元素
通过此方法可以解决 Top-K 问题。
总结
本篇文章详细介绍了堆的实现方法，篇幅较长，难免出现纰漏，如果发现问题，欢迎大家指正。如果绝对本篇文章对你有所帮助，还请三连，您的支持是我最大的动力，谢谢。
