数据结构——堆（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和j
		int 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];

	// 减少堆中元素的数量，并将最后一个元素置为0
	mh->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;
}

测试结果：