堆

发表于 分类于
本文详细讲解了堆的结构和操作用C语言的基本实现

前言

堆是一种完全二叉树，所以在讲解堆之前，会先讲解树和二叉树的概念

树

概念

树是一种非线性的数据结构，它是由n（n>=0）个有限节点组成的一个具有层次关系的集合，把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，叶朝下的
 
根节点是一个特殊的节点，根节点没有前驱节点
 
除根节点外，其余节点被分成M(M>0)个互不相交的集合，其中每个集合又是一棵结构与树类似的子树。每棵子树的根节点有且只有一个前驱节点，可以有0个或多个后继节点
 
因此，树是递归定义的
 

名称 解释
节点的度 一个节点含有的子树个数称为该节点的度
叶节点 度为0的节点
分支节点 度不为0的节点
父节点 若一个节点含有子节点，则这个节点称为其子节点的父节点
子节点 一个节点含有的子树的根节点称为子节点
兄弟节点 具有相同父节点的节点互称为兄弟节点
树的度 一棵树中最大的节点的度称为树的度
节点的层次 从根开始定义起。根为第1层，根的子节点为第2层，以此类推
树的深度或高度 树中节点的最大层次
节点的祖先 从根到该节点所经分支上的所有节点
子孙 以某节点为根的子树中任意节点都称为该节点的子孙

结构

树的结构示意图

注意，
树形结构中，子树之间不能有交际，否则不是树
除了根节点外，每个节点有且仅有一个父节点
一棵N个节点的树，有N-1条边

左孩子，右兄弟表示法

无论有多少个孩子，child指向左边开始第一个孩子，其余的孩子从第一个孩子开始依次用brother指向

1
2
3
4
5
6
struct TreeNode
{
	int val;
	struct TreeNode* leftchild;
	struct TreeNode* rightBrother;
};

对于上面例图中的树，用左孩子右兄弟表示法，是如下结构
树结构

二叉树

概念

一棵二叉树是节点的一个有限集合，该集合：
1.或者为空
2.由一个根节点加上两棵别称为左子树和右子树的二叉树组成

满二叉树：一个二叉树，如果每层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树有K层，且节点总数为2^k^-1,则他就是满二叉树

完全二叉树：完全二叉树是效率很高的数据结构，是由满二叉树引出来的，对于深度为k，节点数为n的二叉树，当且仅当每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称之为完全二叉树，满二叉树是一种特殊的完全二叉树
满，完全二叉树
二叉树不存在度大于2的节点
二叉树的子树有左右之分，次序不能颠倒，所以二叉树是有序树
完全二叉树最后一层不满时，从左到右必须连续

结构

二叉树结构图
二叉树根节点的左右子树如下
根节点的左右子树

数组存储

逻辑结构：想象成树状的
物理结构：通过数组存储
数组存储

为了用下标快速查找父亲和孩子，可以用数组存储二叉树
假设父亲在数组中的下标是i
左孩子在数组中的下标是2*i+1
右孩子在数组中的下标是2*i+2

因为不完全二叉树用数组储存会有空间浪费，因此数组只适合表示完全二叉树，而实际使用时只有堆会用数组储存数据

链式存储

二叉树的链式存储是指用链表来表示二叉树。

通常每个节点由三个区域组成——数据域和左右指针域，这就是常说的二叉链。

然而链式结构还有三叉链，第三条链指向的是父节点，这种结构在高阶数据结构才会使用到，例如红黑树。

本篇文章主要讲解初阶结构，在后面会另开文章详细探讨二叉树的链式存储和三叉链

堆

堆是一种完全二叉树

(小堆示意图)
![小堆](pic_7.png) **
**小堆任何一个父亲 <= 孩子**
**
(大堆示意图)
![大堆](pic_8.png) **
**大堆任何一个父亲 >= 孩子**
**

大堆和小堆不能看作升序和降序排列，大小的关系只存在于父亲和孩子之间

堆的代码实现

结构

前面讲到，本篇文章的讲解的是数组储存结构的堆，所以在堆的结构中需要一个数组
因为堆的大小是不固定的，所以需要用size记录堆内元素个数，用capacity记录当前数组的容量

1
2
3
4
5
6
7
typedef int HPDataType;//便于修改储存的数据类型
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

初始化

1
2
3
4
5
6
7
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

销毁

1
2
3
4
5
6
7
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

交换数值

按照正常的思考逻辑，应该先写插入删除函数，再去完成被调用的向上向下调整函数，然后出于综合考量，再将调整函数中的数值交换封装成函数
但是考虑到这种思维跳转会将文章打乱，为了让文章整体完整，我将代码顺序做了调整

因为这是数组储存，所以在元素顺序变动的时候需要用到交换数值函数，具体如下

1
2
3
4
5
6
void Swap(HPDataType* p1,HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

向上调整

向上调整用于在插入数据时，将数据按照大小堆的规律调整到合适的位置

下图是一个小堆，我们以它为例：
例1
小堆说明父亲小于孩子，所以当插入新元素时，需要不断的将新元素与父亲进行比较。如果孩子<父亲**，那么**交换**两者，如果**孩子>=父亲就不需要继续调整。插入新元素最坏的情况是，新元素比所有的父亲都小，那么这个新元素需要不断与父亲交换，直到新元素成为堆顶。我们假设对这个小堆插入20
小堆过程
看完图解相信你很容易就可以理解向上调整的基本逻辑。那如果是大堆该怎么操作呢？只需要修改交换孩子和父亲的条件为孩子>父亲即可。

1
2
3
4
5
6
7
8
9
10
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;//记录父亲的下标
	while (a[child] < a[parent])//比较父亲和孩子
	{
		Swap(&a[child], &a[parent]);//交换父亲和孩子
		child = parent;//将孩子的下标修改外原来的父亲的下标
		parent = (child - 1) / 2;//重新计算父亲的下标
	}
}

这里有3点要注意：
1.代码中交换父亲和孩子的条件是根据大小堆而定的，并不是固定的

2.同一个父亲的两个孩子下标是不同的，但是计算父亲下标时为不需要区分左右孩子，因为C语言中除号是取整的，左右孩子下标只差1，反推父亲下标时除以的是2，相差的1不足以让商产生变化。
放在具体的例子中，假设左右孩子是1、2，那么左孩子推父亲下标(1-1)/2 = 0，右孩子推父亲下标(2-1)/2 = 0

3.或许聪明的读者你注意到了，这个函数的接口第一个参数接收的是储存堆数据的数组，明明可以直接将堆的整体传入，为什么只传入数组呢？
我在这里留一个伏笔，你可以在后面的建堆算法中找到答案

向下调整

向下调整用于在删除数据时，将数据按照大小堆的规律调整到合适的位置

在讲解向下调整之前，我需要先解释一下删除数据：
对于用数组存储的堆，如果仅仅删除尾部数据，可以直接修改size的大小让尾部无法被访问，但是对于堆来说删掉尾部是没有意义的，删除操作对于堆来说是删除堆顶

堆顶在数组中就在首元素位置，那么可以通过用后面的数据覆盖前面的数据来做到删除堆顶吗？可以，但是不合理。如果一个堆拥有大量的数据，那么通过遍历来覆盖堆顶是十分消耗性能的。

前面讲到过，堆只需要维持父亲和孩子的大小关系即可，所以只要保住这一前提，可以修改除了堆顶以外的其他元素顺序。此时我们只需要找到一个十分容易获取的值来替代堆顶，然后将这个值从堆顶开始向下调整即可，不约而同的我们肯定都能想到数组尾部的值，这个值只需要取下标size-1即可拿到。

接下来我们书归正题，回到当前的向下调整函数：
继续以小堆为例
例2
上图就是向下调整的具体演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void AdjustDown(HPDataType* a, int size, int parent)
{
	//假设左孩子小
	int child = parent * 2 + 1;//获取孩子下标
	while (child < size)//保证孩子的下标不超过限制
	{
		//找到小的孩子
		if (child+1 < size && a[child] > a[child + 1])//标注1
		{//右孩子下标不超过限制的条件下，左孩子小于右孩子
			++child;
		}
		if (a[child] < a[parent])//标注2
		{//最小孩子的值小于父亲的值
			Swap(&a[child], &a[parent]);//交换
			parent = child;//将父亲的下标修改为之前孩子的下标
			child = parent * 2 + 1;//重新计算孩子的下标
		}
		else
		{//如果父亲大于孩子，直接跳出循环
			break;
		}
	}

}

关于向下调整需要注意的是：
1.代码中标注1和标注2的条件写法是不固定的，需要视具体的大小堆来决定
2.向下调整的函数接口同样接收的是数组而不是堆指针

插入

因为数据的大小是固定的，为了方式访问错误和数组溢出，需要先判断元素个数是否等于或超过数组容量，如果超过需要使用realloc扩容
扩容之后在数组尾插入新的数据，并增加size
最后将新数据向上调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void HPPush(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,newcapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}
	//插入新数据
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}

删除

前面在向下调整中讲到，需要先将堆顶数据和最后一个数据交换，并且将size-1，让其无法被访问到
然后将堆顶数据向下调整

1
2
3
4
5
6
7
8
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

获取堆顶

1
2
3
4
5
6
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

判空

1
2
3
4
5
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

建堆算法——堆排序

堆排序是非常高性能的排序

大家都知道的冒泡排序是一种最最基础的排序法，实际上冒泡排序的性能很低(时间复杂度为：O(N^2^))，在大量数据的实际应用中是不会使用的，因此就诞生了更多的排序方式，堆排序就是其中之一

聪明的读者，你可能是一步步从上面学下来的，又或许是直接前来寻找伏笔的答案

那么我直接揭晓答案：堆排序可以直接对数组排序，排序的对象不一定是堆，所以传入数组即可

排序1

时间复杂度为：O(N*logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void HeapSort_1(int* a,int n)
{
	//降序，建小堆
	//升序，建大堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		//堆顶一定是最小或最大值
		//根据建的大小堆对应升降序
		Swap(&a[0], &a[end]);
		AdjustDown(a, end--, 0);
	}
}

排序2

时间复杂度为：O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void HeapSort_2(int* a, int n)
{
	//从最后一个节点的父亲开始倒着排成大堆或小堆
	for (int i = (n - 1 - 1)/2;i >= 0;i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end--, 0);
	}
}

结语

本篇文章旨在讲解数组存储结构的堆，链式存储的堆和更高阶的结构将在之后完成

因为文章篇幅较长，并且堆排序原理有一定难度，我会在之后另起文章讲解，有需要的朋友可以在评论区留言或私信给我，看到之后我会尽快更新相关讲解

如果文章内容有误，欢迎指出