堆（C语言实现）

1.堆的概念

如果有一个关键码的集合，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，孩子节点都不大于父节点的称为小堆，孩子节点都不大于其父节点的称为大堆

图示：

由此可以看出：任何数组都可以看做完全二叉树，但不一定是堆

2.堆的性质

1.堆中某个节点的值总是不大于或不小于其父节点的值
2.堆总是一棵完全二叉树
3.孩子节点和父亲节点下标的关系：

• parent = (child - 1) / 2
• leftchild = parent * 2 + 1
• rightchild = parent * 2 + 2

3.堆的结构

堆总是一棵完全二叉树，堆是用数组来存储的

typedef int HPDataType;//数据类型
typedef struct Heap
{
	HPDataType* a;//数组
	int size;//数据个数
	int capacity;//容量
}HP;
1
2
3
4
5
6
7

4.接口实现

4.1初始化堆

将数组指针指向NULL，将数据个数和容量置零方便后面统计和判断容量，这里断言php是防止人为不小心传入了空指针

//初始化堆
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;// 指空
	php->size = php->capacity = 0;// 置零
}
1
2
3
4
5
6
7

4.2销毁堆

释放掉数组，并将数组指针指空，将数据个数和容量置零即可

//销毁堆
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);//释放
	php->a = NULL;//指空
	php->size = php->capacity = 0;//置零
}
1
2
3
4
5
6
7
8

4.3打印堆内元素

遍历数组将其内的元素打印出来即可

//打印堆内元素
void HeapPrint(HP* php)
{
	assert(php);	
	//遍历打印
	for(int i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

4.4向上调整

将孩子节点的数据和其父结点的数据进行比较，若孩子节点的数据大于（小于）父节点的数据就交换并继续向上调整，直到根结点（数组中下标为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])
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

4.5向堆中插入数据

首先创建一个新节点，并判断数组是否需要扩容，然后直接向数组尾部插入一个数据，将该数据向上调整（保证结构继续是个堆）即可

//向堆中插入数据
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//判断扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		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++;//数据个数+1
	AdjustUp(php->a, php->size - 1);//从尾节点开始向上调整
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.6向下调整

将孩子节点的数据和其父结点的数据进行比较，若孩子节点的数据大于（小于）父节点的数据就交换并继续向小调整，直到最后一个节点（数组中的最后一个的元素）就停止，这里对父子节点的比较是根据堆是大堆还是小堆来决定的

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;//默认是左孩子
	while (child < n)
	{
		//确认child指向大的(小的)那个孩子
		//if (a[child + 1] > a[child] && child + 1 < n)
		if (a[child + 1] < a[child] && child + 1 < n)
		{
			++child;//换成右孩子
		}
		//孩子大于(小于)父亲，就交换并继续向下调整，反之则调整结束
		//if (a[child] > a[parent])
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.7删除堆顶元素

将堆顶元素和堆尾数据元素交换并删除堆尾(此时堆尾数据也就是堆顶数据），再从根节点开始向下调整（保证它继续是个堆）即可，这里需要断言堆为空的情况，为空不能删

//删除堆顶元素
void HeapPop(HP* php)
{
	assert(php);
	//断言堆为空
	assert(php->size > 0);
	//交换堆顶元素和堆尾元素
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;//数据个数-1
	AdjustDown(php->a, php->size, 0);//从根节点开始向下调整
}
1
2
3
4
5
6
7
8
9
10
11

4.8查看堆顶元素

数组首元素就是堆顶元素，直接将其返回即可，这里需要断言堆为空的情况，为空无堆顶元素

//查看堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	//断言堆为空
	assert(php->size > 0);
	//返回数组首元素（堆顶元素）
	return php->a[0];
}
1
2
3
4
5
6
7
8
9

4.9统计堆内数据个数

结构体中的size就是有效数据的个数，直接将其返回即可

//统计堆内数据个数
int HeapSize(HP* php)
{
	assert(php);
	//返回有效数据个数
	return php->size;
}
1
2
3
4
5
6
7

4.10判断堆是否为空

如果堆内的有效数据个数为0，则堆为空，直接返回其布尔值即可

//判断堆是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	//有效数据个数为0则堆为空
	return php->size == 0;
}
1
2
3
4
5
6
7

4.11堆的构建

我们可以人为传入一个数组来建堆，首先需要开辟一个与传入的数组大小相同的空间，用来将数组中的内容复制到该空间中，然后从最后一个元素的父节点开始（(size-1-1)/2）依次向前可以遍历到每颗子树的父节点，并对每颗子树向下调整

//堆的构建
void HeapCreate(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//将数组复制到开辟的空间中
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;

	//建堆算法
	//从最后一个元素的父节点开始依次向前可以遍历到每颗子树的父节点
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(php->a, n, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

图解：

---

堆的实现到这里就介绍结束了，期待大佬们的三连！你们的支持是我最大的动力！
文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正。