数据结构——堆（C语言）

基本概念：

1、完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。

2、满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。

什么是堆？

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆中父子节点结构的性质：在二叉树中，若当前节点的下标为 i，则其父节点的下标为 i/2，其左子节点的下标为 i*2，其右子节点的下标为i*2+1；

堆的插入：

每次插入都是将先将新数据放在数组最后，由于从这个新数据的父结点到根结点必然为一个有序的序列，现在的任务是将这个新数据插入到这个有序序列中——这就类似于直接插入排序中将一个数据并入到有序区间中。

我们通过一个插入例子来看看插入操作的细节。我们将数字 16 插入到这个堆中：

如图所示，将16插入堆中

堆的数组是： [ 10, 7, 2, 5, 1 ]。

第一步是将新的元素插入到数组的尾部，数组变成：[ 10, 7, 2, 5, 1, 16 ]；

插入后相应的树就变成了：

16 被添加最后一行的第一个空位。

不行的是，现在堆属性不满足，因为 2 在 16 的上面，我们需要将大的数字在上面（这是一个最大堆）

为了恢复堆属性，我们需要交换 16 和 2。

现在还没有完成，因为 10 也比 16 小。

我们继续交换我们的插入元素和它的父节点，直到它的父节点比它大或者我们到达树的顶部。这就是所谓的 shift-up，每一次插入操作后都需要进行。它将一个太大或者太小的数字“浮起”到树的顶部。

最后我们得到的堆：

现在每一个父节点都比它的子节点大。

最大堆：

构造最大堆

原始数据为a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用顺序存储方式，对应的完全二叉树如下图所示：

基本思想：
首先将每个叶子节点视为一个堆，再将每个叶子节点与其父节点一起构造成一个包含更多节点的对。

所以，在构造堆的时候，首先需要找到最后一个节点的父节点，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕，这样最大堆就构造完毕了。
假设树的节点个数为n，以1为下标开始编号，直到n结束。对于节点i，其父节点为i/2；左孩子节点为i*2，右孩子节点为i*2+1。最后一个节点的下标为n，其父节点的下标为n/2。
我们边针对上边数组操作如下图所示，最后一个节点为7，其父节点为16，从16这个节点开始构造最大堆；构造完毕之后，转移到下一个父节点2，直到所有父节点都构造完毕。

堆的构造：

数组，count表示内容大小，maxSize表示最大容量。
堆的判空、返回大小、初始化都很简单，直接返回性质（具体看最后代码）。
入堆：入堆需要判断他的大小，方法是：先将他放在最后面的位置（如图），然后依次和他的父亲比较，只要比父亲大，就交换。
出堆：直接取走顶端元素（arr[1]），然后把最后的元素挪到最前面，然后把它进行下移的操作。最后把数组最后一个元素删掉，并且count - 1就完成了。

具体代码

头文件：

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int HeapDataType;typedef struct MaxHeap {HeapDataType* data;int count;int MaxSize;
}MH;//-----------堆的构建等等方法
int size(MH* mh);//返回堆大小
int isEmpty(MH* mh);//判空
void initMaxHeap(MH* mh, int size);//初始化堆
void initMaxHeap2(MH* mh, int size, HeapDataType* arr);//第二种初始化堆,heapify算法
void AdjustUp(MH* mh, int k);//上移元素
void AdjustDown(MH* mh, int k);//下移操作
void insertMaxHeap(MH* mh, HeapDataType value);//插入元素
HeapDataType TopK(MH* mh);//弹出元素
void TestMaxHeap();//测试函数

堆：

#include"heap.h"//返回堆大小
int size(MH* mh) {return mh->count;
}//判空
int isEmpty(MH* mh) {if (mh->count == 0) {return 0;}else {return mh->count;}
}//下移(构建最大堆)
void AdjustDown(MH* mh, int k)/*k为当前节点的索引*/{while (k * 2 <= mh->count)//只要当前节点有左孩子{int j = k * 2;//记录左孩子节点索引if (j + 1 <= mh->count && mh->data[j] < mh->data[j + 1])//如果右孩子存在且右孩子比左孩子大{j = j + 1;//记录右孩子节点索引}if (mh->data[k] > mh->data[j])//如果节点比孩子大{break;//不交换，已经是一个最大堆}//否则交换k和jint tmp = mh->data[k];mh->data[k] = mh->data[j];mh->data[j] = tmp;k = j;//移动记录节点到交换后的子孩子节点}
}//初始化堆
void initMaxHeap(MH* mh, int size) {mh->MaxSize = size;//设定堆的最大容量mh->data = (HeapDataType*)malloc((mh->MaxSize + 1) * sizeof(HeapDataType));//从1开始存储mh->count = 0;
}// 上移元素，调整堆中元素的顺序，确保堆的性质（最大堆）
void AdjustUp(MH* mh, int k) {// 当k不是堆的根节点且当前节点比父节点大时while (1 < k && mh->data[k / 2] < mh->data[k]) {// 交换当前节点和其父节点的值int tmp = mh->data[k / 2];   // 保存父节点的值mh->data[k / 2] = mh->data[k]; // 将当前节点的值赋给父节点mh->data[k] = tmp;             // 将父节点的值赋给当前节点// 更新k，移动到父节点的位置，继续检查堆的性质k /= 2; // 父节点的索引是当前节点索引的一半}
}//插入元素
void insertMaxHeap(MH* mh, HeapDataType value) {//看看有没有满assert(mh->count + 1 <= mh->MaxSize);//count为最后一个元素mh->data[mh->count + 1] = value;mh->count++;AdjustUp(mh, mh->count);//上移到合适位置
}// 弹出堆顶元素，并调整堆，使堆的性质得以保持
HeapDataType TopK(MH* mh) {// 确保堆中至少有一个元素，防止操作空堆assert(mh->count > 0);// 获取堆顶元素（最大值）HeapDataType res = mh->data[1];// 将堆中最后一个元素移到堆顶mh->data[1] = mh->data[mh->count];// 减少堆中元素的数量，并将最后一个元素置为0mh->count--;mh->data[mh->count + 1] = 0;// 将堆顶元素下移到正确的位置，恢复堆的性质AdjustDown(mh, 1);// 返回被弹出的堆顶元素return res;
}

测试函数：

int main() {// 创建一个最大堆MH mh;initMaxHeap(&mh, 10); // 初始化最大堆，最大容量为10// 测试插入元素insertMaxHeap(&mh, 10);insertMaxHeap(&mh, 20);insertMaxHeap(&mh, 15);insertMaxHeap(&mh, 30);insertMaxHeap(&mh, 5);printf("堆的大小: %d\n", size(&mh));  // 输出堆的大小printf("堆是否为空: %d\n", isEmpty(&mh)); // 输出堆是否为空// 测试弹出堆顶元素printf("堆顶元素: %d\n", TopK(&mh));  // 弹出堆顶元素并输出printf("堆的大小: %d\n", size(&mh));  // 输出堆的大小// 弹出剩余元素while (isEmpty(&mh)) {printf("弹出的堆顶元素: %d\n", TopK(&mh));}return 0;
}

测试结果：