【数据结构】详解二叉树之堆

失败只是暂时停止成功，假如我不能，我就一定要；假如我要，我就一定能！💓💓💓

✨说在前面

🍋知识点一：树的概念和结构

• 🌰1.什么是树？

• 🌰2.树的相关概念

• 🌰3.树的表示方法

• 🌰4.树在实践中的运用

🍋知识点二：二叉树的概念和结构

• 🌰1.什么是二叉树？

• 🌰2.二叉树的性质

• 🌰4.二叉树的存储结构

🍋知识点三：堆

• 🌰1.什么是堆？

• 🌰2.堆的基本操作

•🔥堆的初始化

•🔥堆的扩容

•🔥堆的向上调整算法

•🔥堆的插入

•🔥堆的向下调整算法

•🔥堆的删除

•🔥取堆顶数据

•🔥堆的数据个数

•🔥判断堆是否为空

•🔥堆的销毁

• 🌰3.堆的应用

•🔥堆排序

•🔥TOP-K问题

• ✨SumUp结语

✨说在前面

亲爱的读者们大家好！💖💖💖，我们又见面了，到现在为止，我们已经学习了很多的数据结构，从最开始的顺序表，到栈和队列。从这篇开始，我们将进入二叉树这一数据结构的学习。不同于之前的数据结构，二叉树的知识比较抽象，需要大家有比较好的想象和思考能力~

今天我们将要学习二叉树中堆的内容，那什么是二叉树，什么是堆，他们用什么来实现，又有什么作用呢？我们今天就解开它神秘的面纱，详细剖析这个新的数据结构吧~

博主主页传送门：愿天垂怜的博客

🍋知识点一：树的概念和结构

• 🌰1.什么是树？

树是数据结构中的一种，且其属于非线性数据结构结构的一种，我们前文所提到的数据结构多数都是线性的，这也是较为简单的数据结构，而树属于非线性数据结构，也是概念极多的一类。

下面是我们生活中所说的一颗树：

那我们数据结构中的数和现实中的树有什么相似的地方呢？又有什么区别呢？

树的定义：由n（n>=0）个有限结点组成一个具有层次关系的集合。如果n=0，那么它就是一颗空树。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

如图所示，为一颗树：

根结点：根节点没有前驱结点。
除根节点外，其余结点被分成是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
因此，树是递归定义的。

同时，我们要注意子树不可以相交。

• 🌰2.树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图，10的度为2

叶节点（终端节点）：度为0的节点称为叶节点；如上图中的5、13...为叶节点

分支节点（非终端节点）：度不为0的节点；如上图中的20、15...为分支节点

父节点（双亲节点）：若一个节点含有子节点，则称这个节点为其子节点的父节点；如上图，10是5的父节点

子节点（孩子节点）：一个节点含有的子树的根节点称为该节点的子节点；如上图，5和20是10的子节点

兄弟节点：具有相同的父节点的节点互称为兄弟节点；如上图5和20、15和30分别互为兄弟节点

树的度：一棵树中，最大的节点的度称为树的度；如上图，数的度为2

节点的层次：从根开始定义起，根为第一层，根的子节点为第二层，以此类推

堂兄弟节点：双亲在同一层的节点互为堂兄弟节点；如上图中的13和28互为堂兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上度，10是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙；如上图，所有节点都是10的子孙

森林：由m（m>0）可互不相交的树构成的结合称为森林

• 🌰3.树的表示方法

树的结构相对于线性表来说就复杂了许多，要存储表示起来就比较麻烦了，既要保存数据域，也要保存节点与节点之间的关系，实际上数有很多种表示方式，如：双亲表示法，孩子表示法，双亲表示法以及孩子兄弟表示法等。

我们在这里就简单了解一下最常用的孩子兄弟表示法：

我们使用两个指针，一个专门用来指向下一层的子节点，另一个指针用来指向同一层的兄弟节点，这样就比较方便地表示出了树的结构：

具体代码：

typedef int TDataType;

typedef struct TreeNode
{
	TDataType* val;//节点中的数据域
	struct TreeNode* leftchild;//第一个孩子节点
	struct TreeNode* rightbrother;//指向下一个兄弟节点、
}TNode;

• 🌰4.树在实践中的运用

树在实践中的应用--表示文件系统的目录树结构。

🍋知识点二：二叉树的概念和结构

• 🌰1.什么是二叉树？

二叉树是n(n>=0)个结点的有限集合，该集合或为空集（称为空二叉树），或由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

二叉树的每个节点最多只能有两个子节点。

下面就是一棵二叉树：

从上图可以看出：

1.二叉树不存在度大于2的节点

2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

🔥特殊二叉树

1.慢二叉树：一个二叉树，如果它的每一层节点数都达到最大值，则这个二叉树就是慢二叉树。也就是说，如果一个二叉树的层数为K，且总结点数是 $2^{K}-1$ ，则他就是慢二叉树。

2.完全二叉树：完全二叉树是效率很高的数据机结构，完全二叉树是由满二叉树引出来的。对于深度为K的，有n个节点的二叉树，当且仅当其每一个节点都与深度为K的慢二叉树中编号从1至n的节点一一对应时称之为完全二叉树。

注意：的是慢二叉树是一种特殊的完全二叉树。

• 🌰2.二叉树的性质

1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 $2^{(i-1)}$ 个节点.

2.若规定根节点的层数为1，则深度为h的二叉树的最大节点数是 $2^{h}-1$ .

3.对任何一棵二叉树，如果度为0的叶节点个数为 $n_{0}$ ，度为2的分支节点个数为 $n_{2}$ ，则有 $n_{0}$ = $n_{2}$ + 1.

4.若规定根节点的层数为1，则具有n个节点的满二叉树的深度 $h=log_{2}(n+1)$ （ps： $h=log_{2}(n+1)$ 是以2为底，n+1的对数）.

5.对于具有n个节点的完全二叉树，如果按照从上至下从左至右的数组顺序队所有节点从0开始编号，则队与序号为i的节点有：

🔥若i > 0，i位置的节点的父亲节点：(i - 1) / 2；i = 0，i为根节点编号，无双亲节点

🔥若2i + 1 < n，左孩子序号：2i + 1，若2i + 1 > n，则无左孩子

🔥若2i + 2 < n，右孩子序号：2i + 2，若2i + 2 > n，则无右孩子

• 🌰4.二叉树的存储结构

二叉树一般可以使用两种结构存储，一种是顺序结构，一种是链式结构。

1.顺序存储

顺序存储结构就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不完全二叉树会有空间的浪费。而现实中只有堆才会使用数组来存储。二叉树的顺序存储结构在物理上是一个数组，在逻辑上是一棵二叉树。

2.链式存储

二叉树的链式存储是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个节点由三个域构成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习的一般都是二叉链。

具体代码如下：

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
	struct BinTreeNode* left; // 指向当前节点左孩子
	struct BinTreeNode* right; // 指向当前节点右孩子
	BTDataType data; // 当前节点值域
};
// 三叉链
struct BinaryTreeNode
{
	struct BinTreeNode* parent; // 指向当前节点的双亲
	struct BinTreeNode* left; // 指向当前节点左孩子
	struct BinTreeNode* right; // 指向当前节点右孩子
	BTDataType data; // 当前节点值域
};

🍋知识点三：堆

• 🌰1.什么是堆？

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常对堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。这里数据结构中的堆和操作系统中的堆是两个概念，前面还介绍学习过数据结构中的栈和内存中的栈两个概念也不同哈~

如果有一个关键字集合 $K=\left \{ { k_{0},k_{1},k_{2},...,k_{(n-1)}} \right \}$ ，将它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 $k_{i}\leq k_{2i+1}$ 且 $k_{i}\leq k_{2i+2}$ （ $k_{i}\geq k_{2i+1}$ 且 $k_{i}\geq k_{2i+2}$ ） $i=0,1,2......$ ，则称之为小堆（或大堆）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

其实说白了就是所有父亲节点比子节点的值大就是大堆，所有父亲节点比子节点的值小就是小堆。

我们知道，我们实际操作的是数组，想象操作的是二叉树。所以我们需要堆这个数据结构的话，需要包含数组、数组的长度和它的空间，我们可以用动态顺序表来实现堆。，具体代码：

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}HP;

• 🌰2.堆的基本操作

我们以小堆为例，展示堆的基本操作。

•🔥堆的初始化

堆的初始化和动态顺序表一样，将数组arr初始化为空，再将有效长度和空间都初始化为0.

void HPInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

•🔥堆的扩容

与动态顺序表和栈的扩容相同，我们也已经很熟悉了。由于这个不是堆的基本操作，我们加上static，用来辅助该文件内的其他函数。

static void HPCheckCapacity(HP* php)
{
	if (php->size == php->capacity)
	{
		int NewCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* temp = (HPDataType*)realloc(php->arr, NewCapacity * sizeof(HPDataType));
		if (!temp)
		{
			perror("realloc operation failed");
			exit(1);
		}
		php->arr = temp;
		php->capacity = NewCapacity;
	}
}

•🔥堆的向上调整算法

当我们在堆的末尾添加上一个数据后，形成的新的完全二叉树可能不满足堆的性质，这个时候我们需要将最后一个数据进行调整，使得调整之后的完全二叉树仍然是大堆或者小堆。

代码如下：

//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

//堆的向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[parent] < arr[child])
		{
			Swap(arr + parent, arr + child);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

•🔥堆的插入

有了向上调整算法的基础，对于堆的插入操作就很简单了。堆的插入，就是在堆的末尾，也就是数组的末尾插入新的节点，再将这个节点向上调整，使之调整后仍然是之前的大堆或小堆。具体代码如下：

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	HPCheckCapacity(php);
	php->arr[php->size++] = x;
	AdjustUp(php->arr, php->size - 1);
}

•🔥堆的向下调整算法

当我们需要删除堆顶的数据时，一般需要将堆顶的数据调整到堆的末尾，也就是数组的末尾，让数组的size--就可以了。将堆顶数据调整到堆的末尾，需要用到堆的向下调整算法；或者是根节点换了另外一个值过来，那也不一定满足堆的性质，需要将这个值调整到合适的位置。

具体代码如下：

//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

//堆的向下调整算法
void AdjustDown(HPDataType* arr, int n, int parent)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[parent] < arr[child])
		{
			Swap(arr + parent, arr + child);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

•🔥堆的删除

那么我们理解了堆的向下调整算法，对于堆的删除操作就很简单了。堆的删除就是将堆中根结点和尾节点进行交换，再利用向下调整算法使得调整后仍然是原来的大堆或小堆，但是size减小1。具体代码如下：

void HPPop(HP* php)
{
	assert(php && php->size);
	Swap(php->arr, php->arr + php->size - 1);
	php->size--;
	AdjustDown(php->arr, php->size, 0);
}

•🔥取堆顶数据

不论是大堆还是小堆，堆顶的数据总是在数组的第一个位置。所以我们返回arr[0]就可以了，代码如下：

HPDataType HPTop(HP* php)
{
	assert(php && php->size);
	return php->arr[0];
}

•🔥堆的数据个数

我们实际上操作的是数组，并且以数组（动态顺序表）的形式实现堆，所以堆的数据个数就是有效数据个数size。

int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

•🔥判断堆是否为空

和之前栈的判空基本相同，就是去判断有效数据个数size是否为0。我们可以用布尔类型。

bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

•🔥堆的销毁

和动态顺序表销毁的方式相同。

void HPDestroy(HP* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

• 🌰3.堆的应用

•🔥堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆排序总共分为两个步骤：

1.建堆

升序：建大堆

降序：建小堆

2.利用堆删除思想来进行排序。

我们以升序排列为例，排列一组数据：16，14，10，8，7，9，3，2，4，1。我们实际上操作的是数组，想象的是大堆。

接下来，我们将堆顶（最大的数）和尾（最小的数）交换位置，然后重新调整，得到的新的堆重复刚才的操作即可：

注意：上述20应该改为16 。

具体代码：

void HeapSort(int* arr, int length)
{
	//向下调整建堆O(N)
	for (int i = (length - 2) / 2; i >= 0; i--)
	{
		AdjustDown(arr, length, i);
	}
	while (length - 1)//O(NlogN)
	{
		Swap(arr, arr + length - 1);
		AdjustDown(arr, length - 1, 0);
		length--;
	}
}

在代码中，我们能看到向下调整建堆的过程。也就是说，我们要将数组中存放的数据想象成堆，那么建堆的过程，我们用向下调整建堆，这个过程的复杂度是O(N)，具体推导过程如下：

所以建堆过程的时间复杂度为 O(N)，而后面while循环的时间复杂度为 O(NlogN)，所以堆排序的时间复杂度为 Ο(NlogN)。

•🔥TOP-K问题

有了堆排序的基础，我们可以很轻松地解决TOP-K问题。

TOP-K问题：即求数据中前K个最大（或最小）的元素，一般情况下数据量比较大。

比如：专业前10，名、世界500强、富豪榜、游戏中前100名的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方法就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中）。最佳的方式就是用堆来解决，基本思路如下：

1.用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2.用剩余的N-K个元素一次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

举例：将data.txt文件中的n个随机数中找到最大的前k个。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <stdbool.h>

//创造数据
void CreateData()
{
	int n = 100000;
	srand((unsigned int)time(NULL));
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("fopen operation failed");
		exit(1);
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 1000000;
		fprintf(pf, "%d\n", x);
	}
	fclose(pf);
	pf = NULL;
}

//堆排序
void HeapSort(int* arr, int length)
{
	assert(arr);
	for (int i = (length - 2) / 2; i >= 0 ; i--)
	{
		AdjustDown(arr, length, i);
	}
	while (length - 1)
	{
		Swap(arr, arr + length - 1);
		AdjustDown(arr, length - 1, 0);
		length--;
	}
}

void TestHeap()
{
	//创建k个数的小堆
	int k = 0;
	printf("请输入k值->");
	scanf("%d", &k);
	int* k_min_heap = (int*)malloc(k * sizeof(int));
	if (k_min_heap == NULL)
	{
		perror("malloc operation failed");
		exit(1);
	}
	FILE* pfout = fopen("data.txt", "r");
	if (pfout == NULL)
	{
		perror("fopen operation failed");
		exit(1);
	}
	//读取文件前k个数
	for (int i = 0; i < k; i++)
	{
		fscanf(pfout, "%d", &k_min_heap[i]);
	}
	for (int i = (k - 2) / 2; i >= 0; i--)
	{
		AdjustDown(k_min_heap, k, i);
	}
	//读取剩下的n-k个数
	int receive = 0;
	while ((fscanf(pfout, "%d", &receive)) != EOF)
	{
		if (receive > k_min_heap[0])
		{
			k_min_heap[0] = receive;
			AdjustDown(k_min_heap, k, 0);
		}
	}
	HeapSort(k_min_heap, k);
	//遍历后的大堆即为Top—K数
	printf("最大的前%d个数为：", k);
	for (int i = 0; i < k; i++)
	{
		printf("%d ", k_min_heap[i]);
	}
	printf("\n");
}

int main()
{
	CreateData();
	TestHeap();
	
	return 0;
}