【数据结构初阶】树+二叉树+堆的实现+堆的应用

真正的勇士，就是在看清生活的真相后，依旧慷慨面对他所遭受的苦难与挫折。

---

---

一、树

1.1 树的介绍

树是一种非线性的数据结构，它是一种由有限个结点组成的具有层状结构的集合，把它叫做树是因为它看起来像一颗倒挂起来的树，叶子朝下，根root朝上。

其中最上面的结点称之为根节点，而且每一棵子树之间是不能有交集的，否则就不是树状结构了，下面的Linux目录的结构就是我们的树形结构。

1.2 树的重要概念

1.结点的度： 一个结点含有的子树的个数称为该节点的度

2.叶结点或终端结点： 子树个数为0的结点

3.双亲结点或父节点： 如果一个结点有子结点，则这个结点称为子节点的父节点

4.孩子结点或子结点： 一个结点含有的子树的根结点就是这个结点的子结点

5.结点的层次： 从根开始定义，根为第一层，根的子节点为第二层，一次类推

6.结点的祖先： 从树的根节点开始一直到这个结点所经过的路径上所有的结点就是这个结点的祖先。

7.子孙： 以某一结点作为根结点的子树下的所有结点都是这个根结点的子孙

8.森林： 多棵互不相交的树组成的集合称之为森林。

例如Linux中的ls指令其实就是将当前所处根结点的所有子节点全部列出来

1.3 树的表示(左孩子右兄弟)

树的结构在表示时，不仅要存储值，还要链接其每个结点之间的关系，但我们不知道每个结点的度是多少，但不要担心，问题总会有解决的办法的，下面就来说一下左孩子右兄弟表示法的精妙所在。

我们不管那么多，每个结点只能有一个孩子，剩下的子节点就跟父节点没关系了，全靠他的第一个孩子来连接，直到一个孩子的brother指到空指针，这一层就完事了。
后面的也依次类推。

二、二叉树

2.1 二叉树的介绍

一棵二叉树是结点的一个有限集合，该集合可以为空或由两棵子树构成，子树分别称为左子树和右子树，并且二叉树中结点的度是不可以超过2的，也就是任意一个结点的子节点个数必须小于等于2。

任意的一棵二叉树都是由下面的几种情况复合而成的。

只要一棵树的最大度小于等于2，我们就可以把这棵树称之为二叉树，空树，只有根节点等都可以称之为二叉树。

当然二叉树中也有一些特殊的树，分别是完全二叉树和满二叉树。

满二叉树就是除叶结点之外的结点的度都是2.

完全二叉树其实就是特殊的满二叉树，只要满足最后一行是连续的叶结点，中间不可以空开，除最后一层外其他层满足满二叉树的特点，这样的树我们称之为完全二叉树。但完全二叉树最后一层最少都得有一个结点。

2.2 二叉树的性质

1.满二叉树的结点个数：2^h-1(h代表树的层数)

2.完全二叉树的结点个数：最多个数：2^h-1 最少个数：2^(h-1)

3.对于任何一棵二叉树，假设叶结点个数为n0，度为2的结点个数为n2，则有结论n0=n2+1，也就是叶结点个数永远比度为2结点个数多1

4.完全二叉树度为1的结点个数要么是1要么是0.

5.父子结点关系：parent=(child-1) / 2 leftcihld=parent2+1 rightchild=parent2+2

6.满二叉树高度为h,节点数是n，h=log(n+1)，我们后面会经常用高度来判断算法的时间复杂度。

三、二叉树的顺序结构及实现

3.1 二叉树的顺序结构

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.2 堆的概念及结构

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

其实堆就是完全二叉树

其实为什么要存在逻辑结构这种东西呢？

其实吧实际在内存当中的存储结构就两种，一种是数组一种是链表，但由于我们生活中的存储模式可不简简单单只有这两种结构，所以我们将这两种基本的存储结构抽象成我们想要的结构，用算法来将其进行实现。

所以其实逻辑结构存在的最大意义就是方便我们理解，如果没有逻辑结构，我们对着生涩的数组裸写代码，是非常容易写错的，所以我们需要逻辑，需要它将抽象的东西变得生动化，可视化，形象化。

3.3 堆(底层就是顺序表)的实现

3.3.1 堆结构体设计+堆的初始化+堆的销毁

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

1
2
3
4
5
6
7
8

其实这里堆结构体就是一个顺序表，我们定义的结构体和顺序表也没什么区别

void HeapInit(HP*php)
//这里初始化开不开辟空间都可以，我们可以选择这里开空间，后面用realloc修改空间大小，也可以这里不开空间，直接后面realloc修改空间
//因为当realloc接收的指针为NULL时，他的作用和malloc是一样的，所以这里开不开辟空间都是可以的
{
	assert(php);
	php->array = NULL;
	php->size = php->capacity = 0;
}
1
2
3
4
5
6
7
8

初始化这里也没什么新奇的东西和之前讲解的链表顺序表等，没什么区别

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

释放掉动态开辟的数组空间，然后将指针置为空，其他变量置为0即可。

3.3.2 堆的插入(附：向上调整算法)+堆的删除(附：向下调整算法)

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->array, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			exit(-1);
		}
		php->array = tmp;
		php->capacity = newCapacity;
	}
	php->array[php->size] = x;
	php->size++;

	AdjustUp(php->array, php->size - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

在插入数据之前我们还是需要先检查空间是否满，如果满了，我们直接扩容就好了。最后我们调用向下调整的接口进行实现堆的调整

void AdjustUp(HPDataType* array, int child)//传过来你插入的孩子的下标
{
	int parent = (child - 1) / 2;
	while (child > 0)//child会被赋值到祖先的位置，这时parent已经越界了，我们的向上调整也就结束了，所以child>0
	{
		if (array[child] > array[parent])
		//如果想要调整为小堆的话，我们只要调整这里的比较符号就可以了，保证树中所有的父亲都小于等于孩子
		{
			Swap(&array[child], &array[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

我们每一次插入新的数据，我们都让这个新的数据和他的父节点进行比较，我们这里默认建的是大堆，所以只要每次插入的孩子结点大于父节点时，我们就将这个子节点向上调整到parent下标的位置，parent继续向上调整到新的parent的位置，等到child的位置到达祖先的位置也就是根节点root的位置时，我们向上调整的循环也就结束了。

多说一句，大家可能有点蒙，为什么child-1除以2就是parent的结点了，不用分情况讨论吗？child的下标既有可能是奇数，也有可能是偶数啊，你不用区分一下吗？

其实是不用区分的，因为/求的是商，我们的偶数和奇数下标经过上面的运算过后，其实结果是一样的。所以在利用孩子找父节点时，只要减1再除以2就OK了。

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);//括号内表达式若判断为假，直接报错，粗暴的方式来解决

	Swap(&php->array[0], &php->array[php->size - 1]);
	php->size--;

	//AdjustDownMe(php->array, php->size -1);
	AdjustDownTeach(php->array, php->size, 0);
}
1
2
3
4
5
6
7
8
9
10
11

我们再删除堆顶数据时，利用了一个小技巧就是，我们将堆顶数据用堆中最小辈分的数据覆盖掉，然后依次向下调整数据的位置，以便保证堆还是大堆，为什么这样做是可行的呢？这样做可以保持根的某一个子树结构不变，我们只要调整另一子树的数据就可以了，而且这个调整还是递归式的，我们的算法时间复杂度是logN。
要知道logN可是非常快的，所以这个算法是非常牛逼的。

void AdjustDownTeach(HPDataType* array, int n, int parent)
{
	int child = parent * 2 + 1;//上来我们就先假设最大的孩子是左孩子

	while (child<n)//我们想的是循环结束的条件，写的是循环继续的条件
	{
		//保证有右孩子的同时，看看我们的假设是否正确，错误就调整
		if (child + 1 < n && array[child + 1] > array[child])
		//如果假设错误，我们将孩子改为右孩子，并且你也有可能没有右孩子，没有右孩子，默认左孩子就是最大的
		//这里其实不用担心没有孩子的问题，因为如果parent没有孩子，child被赋值过后肯定大于n了直接跳出循环了就。
		{
			++child;//将下标自增，左孩子就变为右孩子
		}
		if (array[parent] < array[child])
		{
			Swap(&array[parent], &array[child]);
			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

这里的代码延续了我们之前再做栈和队列的一些面试题时所用到的技巧了，就是假设法，如果假设错了，我们直接利用if语句进行调整就OK了，向下调整也简单，只要我们的parent小于他的子节点，那它就得往下走，不能占顶部的位置，这算法和前面的向上调整也是比较相似的。

3.3.3 取堆顶数据+堆的大小+堆的判空

这几个接口真的是简单的要死，我不想说了，写了这么多数据结构了，今天见的属实是简单的要死。

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->array[0];
}
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.3.4 测试接口

void TestHeap1()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	HP heap;//建一个堆
	HeapInit(&heap);
	for (int i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		HeapPush(&heap, array[i]);//我们的插入模块儿里面，每一次插入之后，都会再重新向上调整一次，以此来保证我们的堆是大堆。
	}
	HeapPrint(&heap);
	HeapPop(&heap);
	HeapPrint(&heap);
	//topK快
	int k = 5;
	while (k--)
	{
		printf("%d ", HeapTop(&heap));//求出topk个数据，大堆中最大的前5个数据
		HeapPop(&heap);
	}
		 
	HeapDestroy(&heap);

}
void TestHeap2()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	HP heap;//建一个堆
	HeapInit(&heap);
	for (int i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		HeapPush(&heap, array[i]);//我们的插入模块儿里面，每一次插入之后，都会再重新向上调整一次，以此来保证我们的堆是大堆。
	}
	HeapPrint(&heap);
	
	
	//topK快
	int k = 5;
	while (!HeapEmpty(&heap))//利用堆顶数据，我们可以打印出来这个数组的降序内容
	{
		printf("%d ", HeapTop(&heap));//求出topk个数据，大堆中最大的前5个数据
		HeapPop(&heap);
	}

	HeapDestroy(&heap);
}
int main()
{
	//TestHeap1();
	TestHeap2();//测试过后我们的数组就被我们排成降序的了

	return 0;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

这里说几句吧，我们可以利用HeapTop接口和HeapPop接口来组合解决topK问题，然后再测试接口里面我们是单独先创建了一个数组，然后利用堆的插入接口，讲这个数组的内容重新插入到我们动态开辟的数组array，这样就实现我们大堆的搭建了。

四、建堆

4.1 向上调整算法（拿子节点向上和父节点比较，更改自己在族谱的地位）

在上一篇博客中，我们在写到堆的实现时，就已经给大家介绍过了向上调整的算法了，我们如果要建大堆，当child的值大于parent时，我们就将两元素进行交换，并且将下标位置进行迭代。进行下一次可能的元素交换。

我们来分析一下这个算法的时间复杂度：我们利用满二叉树来进行分析。

由于最下面一层的结点个数非常多，而且如果是最坏的情况下，每一个结点都需要调整logN次，那最坏的情况其实就是N/2 * logN，忽略常数之后，算法的时间复杂度就是N*logN，因为最后一层的结点个数其实已经相当接近整个二叉树结点个数的一半了，然而这些结点中的每一个结点的最坏调整次数又是这个二叉树中所有结点最狠的，两个最重要的因素合在一块儿了，自然就占这个时间复杂度的最大程度了。

4.2 向下调整算法（拿父结点向下和子节点比较，适用于建堆，效率高）

这个算法是一个非常不错的用来建堆的方法，并且效率很高，虽然实用程度不算太高，但是对于堆这种数据结构来讲是极其牛逼的。
1.如果它用于堆排序中，时间会非常的快
2.它不仅仅可以用于建堆，还可以用于堆的删除，实用范围很广。

分析一下第二点优势： 下图就是向下建堆的图片呈现形式，总结起来就是一句话，如果你要建小堆，那就拿出子节点中最小的结点放到堆顶的位置，如果你要建大堆，那就拿出子节点中最大的结点放到堆顶的位置，当然我们调整的前提一定是，此刻父节点已经不满足我们建堆的要求了，我们才会选择对堆进行调整，如果满足我们肯定是不用进行调整的。
如果要进行堆的删除，我们可以这样做，将堆顶数据和堆最后一个数据交换，然后将数组大小-1，去除掉堆顶的数据，最后再进行向下调整，重新建堆。

下面的两张图片分别是我们的向下调整算法在建堆，删除堆时的使用形式。

//图片分隔符

最后分析一下第一点优势： 这个算法建堆的速度我们是不能大致分析然后得出结果的，我们需要进行细致的计算得出其时间复杂度。

我们先来简单的大致分析一下他的时间复杂度，看能否得出结果。

首先建堆我们是从倒数第二层开始向上移动然后向下调整堆，倒数第二层的结点个数虽然较多，但他们最坏情况下的调整次数却没有多少，因为最坏也就是每个结点调整一次而已。
如果继续往上走，我们的结点个数自然会减少，但二叉树的高度又增加了起来，所以最坏情况下，每个结点的调整次数又增多了，这就为我们进行大致分析带来了难度，因为最重要的两个影响因素始终无法合到一块，我们无法找出决定性的一层。

然而我们的向上调整算法，它最后一层结点个数很多，而且调整次数也多，整个算法的时间基本全耗在最后一层了，我们直接分析最后一层即可。

但现在情况不同了，所以我们需要细致的分析一下这个算法，分析过程如下：

现在我们就可以比较出来了，建堆，向上调整的时间复杂度是O(N*logN)，向下调整的时间复杂度是O(N)，由此可见建堆时，向下调整算法是多么优啊，还不赶快用起来？

五、堆排序

5.1 升序建大堆+降序建小堆

我们可以先想一下，如果我们现在建一个小堆的话，这个小堆的第一个元素正好就是数组元素中最小的，刚好满足我们升序中的第一个元素。但是后面的元素你就没法整了，你无法找出次小的元素了就，除非你利用之前的建堆，取堆顶元素，删除堆顶元素这样一系列的步骤来获取次小的元素之外，你是没有其他办法的。

所以我们选择换个思路进行思考，如果我们建大堆来排升序呢？这样第一个元素就是最大的元素，我们只要将这个最大的元素和堆中最后一个元素进行交换，这样一来，除堆顶位置之外，其他的堆顺序都是没改变的，我们只要将堆顶数据向下调整，重新满足大堆，然后再将这个次大的元素移动到堆的末尾，连续不断的进行这个操作，我们其实就将数组排成一个升序的数组了，与之前的想法不同的是，我们是倒着排升序的从后往前找次大的。

利用向下调整算法先将数组元素排成大堆形式，然后进行排升序的步骤


只要对向下调整算法稍作修改，我们就可以得到升序和降序。

5.2 时间复杂度

算上我们建堆和堆排序这些的总时间来看，时间复杂度是N+N*logN，忽略掉N后，时间复杂度就是N * logN，这相对于冒泡排序是有极大的优化的。

当然堆的优势肯定不在排序上面，快排还是更加实用的，我们后面也会讲到快排，毕竟术业有专攻嘛，堆只是一种值得我们去学习的数据结构，又不是为排序而生的，只是说他有排序这样不俗的功能，我们也需要了解一下。

六、TopK(max)问题

6.1 建K个元素的小堆

这里可能会有人问到为什么不用大堆啊？建大堆的话，我们可以利用取堆顶元素，然后在删除堆顶元素来拿到TopK个元素啊。
这样倒是也行但存在很多不足的地方，比如他的时间复杂度是N+K*logN，而且一旦数据量过大，我们是无法开辟那么大的堆的，因为毕竟内存空间还是有限的。

所以我们采取建k个元素的小堆，我们将剩余的元素进行遍历和我们的小堆堆顶元素进行比较，如果大于我们就将两者进行交换，然后向下调整，重新让这个堆的堆顶变成这K个数里最小的数，等到全部的数遍历完之后，这个小堆中的k个元素也就变成了所有数中最大的k个元素了。

相反，如果我们要求topK中前最小的k个元素，我们建大堆就好了，只要有元素小于堆顶元素我们就让它进堆，等到元素全部遍历完之后，这个大堆中的所有元素也就变成所有数中最小的k个数了。

6.2 代码实现

void TestHeap5()
{
	// 造数据
	int n, k; 
	printf("请输入n和k:>");
	scanf("%d%d", &n, &k);
	srand(time(0));//生成随机数的种子
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	for (size_t i = 0; i < n; i++)
	{
		int val = rand();//这里调用rand生成随机数
		fprintf(fin, "%d\n", val);
	}
	fclose(fin);

	int* minHeap = (int*)malloc(sizeof(int) * k);
	FILE* fout = fopen("Data.txt", "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
	
	for (int i = 0; i < k; i++)//先将随机数放到动态开辟的数组里面
	{
		fscanf(fout, "%d", &minHeap[i]);//scanf读取时默认空格和换行就是分隔符
	}
	//建k个数的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDownTeach(minHeap, k, i);
	}
	int val = 0;
	//开始堆顶数据和数组中剩余数据的比较，若满足条件则替换并向下调整。
	while (fscanf(fout, "%d", &val)!=EOF)
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			AdjustDownTeach(minHeap, k, 0);
		}
	}
	//最后一步打印小堆的内容，出来的正好就是TopK的数据。
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");
	fclose(fout);
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55