【数据结构】二叉树&&优先级队列——堆

2.4 二叉树的存储结构

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

1. 顺序存储

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

2. 链式存储

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

3. 堆

3.1 堆的概念及结构

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

其实任何一个数组都可以看做一颗完全二叉树，但不一定是堆，其孩子和父亲的下标关系为：

• leftchild=parent*2+1

• rightchild=parent*2+2

• parent=(child-1)/2

💕 堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

3.2 堆的实现

3.2.1 堆的创建

这里我们先定义一个表示堆的顺序表来进行存储堆中的数据

typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;
	int size;
	int capacity;
}HP;
1
2
3
4
5
6

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};
1

在这里我们使用的是向上调整算法，从下至上依次调整，最后保证这棵二叉树的每一个子树都是一个堆。

3.2.2 堆的插入

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size) {
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (!tmp) {
			perror("realloc fail::");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size++] = x;
	//向上调整算法
	AjustUp(php->a, php->size - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

如果第一次插入数据，我们就要先先开辟一块空间并且并将结构体中的指针指向这块空间，并将数据插入数组中，我们需要注意的是我们需要在每次插入一个数据后都进行一次向上调整，这样才能保证我们最终构建出来的二叉树是一个堆，下面我们来看一下向上调整算法。

3.2.3 堆的向上调整算法

//向上调整算法/*小堆*/
void AjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])//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

这里我们以小堆的构建为例，我们从堆中的最后一个孩子开始调整，若孩子小于父亲，则将孩子和父亲中的元素交换，交换完成后并将父亲的下标赋给孩子，使得父亲成为新的孩子，并利用这个孩子的下标找到新的父亲的下标，以此循环，直到孩子的下标变为0或者孩子小于父亲为止停止循环，由于我们每次插入一个节点时都要进行向上调整，所以最后将节点全部插入后也就会构成一个小堆了。如果我们建大堆的话只需要将if语句中的判断条件改一下即可。

3.2.4 堆的删除

//堆的删除
void HeapPop(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
7
8
9
10

堆的删除指的并不是删除堆中任意的数据，而是删除堆顶数据后保证他依然是一个堆,但我们如果要是直接将堆顶的数据删除时，就会改变他原来的结构，如图所示：

这时的二叉树结构已经不是一个堆了，如果我们再次从最后一个元素往上调整的话效率将会变得非常差，所以这里我们来一种巧妙的方法：将堆的堆顶元素和最后一个元素进行交换，在将最后一个元素删除，最后将堆顶的元素向下调整使他再次变成一个堆，下面我们来看一下向下调整算法。

3.2.5 堆的向下调整算法

//向下调整算法(大堆)
void AdjustDown(HPDataType* a,int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n) 
	{
		if (child+1<n && a[child + 1] > a[child]) {
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[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

将堆顶和堆的最后一个元素交换后将最后一个元素删除，然后我们就可以从堆顶开始向下调整了，这里我们需要将删除元素后的堆中的元素个数传入函数中来控制循环的结束，从堆顶开始，如果父亲小于左右孩子中大的那个孩子，就将父亲和此孩子交换，然后再将此孩子的下标作为新的父亲，然后算出新的父亲的左孩子的下标，这里我们需要先算出左孩子的下标，如果右孩子大于左孩子，就将左孩子的下标加一，再次进行父亲和孩子比较，如果父亲大于等于孩子或者孩子的下标已经超出了元素个数，则停止循环，此时的堆已经构建成了一个大堆。

3.2.6 建堆的时间复杂度

💕 向上调整建堆时间复杂度

这里我们以满二叉树来举例，如果这颗树深度非常深的话，假设这颗树高为h，最后一层的节点个数比前n-1层的节点个数都多。最后一层节点个数为2^ (h-1)个，每个节点都需要向上调整h-1次，所以最后一层需要调整 2^(h-1)*(h-1)次，化简得2^h*(h-1)/2，又因为在满二叉树中树的高度和节点之间的关系为2^h-1=N,h=log(N+1)，所以经过调整后最后一层节点所需要调整的次数变成了(N+1)*(log(N+1)-1)/2，只保留最高阶项后就是O(N*logN)了。

void UpHeapBuild(int* a, int n)
{
	//向上调整建堆
	for (int i = n - 1; i > 0; i--) {
		AjustUp(a, i);
	}
}
1
2
3
4
5
6
7

💕 向下调整建堆时间复杂度

在这里我们可以得出向下调整建堆的时间复杂度是O(N)，向下调整建堆的效率更高，所以我们建堆的时候强烈推荐使用向下建堆。

void DownHeapBuild(int* a, int n)
{
	//向下调整建堆
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
}
1
2
3
4
5
6
7
8

3.3 堆的完整代码

Heap.h

#pragma once
#include
#include
#include
#include
typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;
	int size;
	int capacity;
}HP;

//堆的初始化
void HeapInit(HP* php);

//堆的销毁
void HeapDestroy(HP* php);

//堆的插入
void HeapPush(HP* php, HPDataType x);

//堆的打印
void HeapPrint(HP* php);

//向上调整算法
void AjustUp(HPDataType* a, int child);

//堆的删除
void HeapPop(HP* php);

//向下调整算法
void AdjustDown(HPDataType* a,int n, int parent);

//取堆顶的数据
HPDataType HeapTop(HP* php);

//堆的数据个数
int HeapSize(HP* php);

//堆的判空
bool HeapEmpty(HP* php);

//交换函数
void Swap(HPDataType* p1, HPDataType* p2);

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

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

//堆的初始化
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

//堆的销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

//堆的打印
void HeapPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++) {
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
向上调整算法(大堆)
//void AjustUp(HPDataType* a, int child)
//{
//	int parent = (child - 1) / 2;
//	while (child > 0)
//	{
//		if (a[child] > a[parent])
//		{
//			Swap(&a[child], &a[parent]);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
/*小堆*/
void AjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size) {
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (!tmp) {
			perror("realloc fail::");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size++] = x;
	//向上调整算法
	AjustUp(php->a, php->size - 1);
}

//向下调整算法(大堆)
void AdjustDown(HPDataType* a,int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n) 
	{
		if (child+1<n && a[child + 1] > a[child]) {
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
/*小堆*/
//void AdjustDown(HPDataType* a, int n, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child < n)
//	{
//		if (child + 1 < n && a[child + 1] < a[child]) {
//			child++;
//		}
//		if (a[parent] > a[child])
//		{
//			Swap(&a[parent], &a[child]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//堆的删除
void HeapPop(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);
}

//取堆顶的数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

// 堆的数据个数
int HeapSize(HP* php)
{
	assert(php);
	assert(php->size > 0);
	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
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void TestHeap1()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		HeapPush(&hp, array[i]);
	}
	HeapPrint(&hp);
	HeapPop(&hp);
	HeapPrint(&hp);
	HeapDestroy(&hp);
}
int main()
{
	TestHeap1();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4. 堆的应用

4.1 堆排序

💕 堆排序即利用堆的思想来进行排序，总共分为两个步骤：

建堆：

升序：建大堆
降序：建小堆

这里我们来看一下为什么升序要建大堆，降序要建小堆：

我们将堆顶的数据和最后一个孩子交换后最后一个孩子就变成了最大的数据，此时我们将堆顶的数据进行向下调整使他再次变成一个大堆，这里我们调整的时候需要将数据的总个数减去1，这样做是因为最后一个数据已经是最大的了，我们在进行下一次向下调整时就不能调整最后一个元素了，就这样当我们将每一次调整后的堆的堆顶和最后一个孩子进行交换并调整，最终数据从后往前就会排列成依次减小的顺序，所以从前往后读他就是升序的顺序了。当然，如果要是降序的话则需要建大堆后再这样操作了。

💕 堆排序的时间复杂度

首先我们使用向下调整算法建堆的时间复杂度为O(N)，然后在每一次交换并向下调整的过程时间复杂度为log(N)，以最后一层为例，最后一层又需要调整N次，所以时间复杂度就为N+N*logN，保留最高阶项，堆排序的时间复杂度为N*logN。

💕 代码实现

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向下调整算法(大堆)
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child]) {
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//堆排序(升序)——建大堆
void HeapsortRise(int* a, int n)
{
	//先建堆
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//排序
	int size = n - 1;
	while (size > 0)
	{
		Swap(&a[0], &a[size]);
		AdjustDown(a, size, 0);
		size--;
	}
}
//打印数组内容函数
void ArrayPrint(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	int n = sizeof(array) / sizeof(array[0]);
	HeapsortRise(array, n);
	ArrayPrint(array, n);
	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
53
54
55
56
57
58
59
60
61
62

4.2 TopK问题

首先我们先来介绍一下什么是TopK问题：

所谓的TopK问题就是在一堆数据中找到前K个最大的元素或者前K个最小的元素

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

💕 思路一：

建立一个N个数的大堆，popK次，依次取堆顶数据，这里每次取堆顶数据后需要将堆顶数据删除掉，这样popK次后，我们就可以取到前K个大的数据或者前K个小的数据。这个方法的时间复杂度分析：首先建堆的时间复杂度为O(N)，然后每次pop堆顶的数据并进行向下调整的时间复杂度为O(logN)，总共popK次，时间复杂度为O(K*logN)，所以总共的。

复杂度分析：

时间复杂度为O(N+K*logN)， 空间复杂度：他们是存放在内存中的，所以为空间复杂度为O(1)。

💕 思路二：

如果数据量很大的话，那么我们的数据就不能够放到内存中，所以就只能放入磁盘中，所以第二种思路就是：建立一个K个数的小堆，依次遍历数据，遇到比堆顶数据大的就替换堆顶，再向下调整堆，最后这个小堆中就是最大的K个数。

这里我们需要注意的是如果我们要取最大的前K个数时，一开始需要建立一个K个数的小堆，一定不能建大堆，如果建大堆的话如果一开始堆顶就是最大的数，当我们遍历的时候，遇到的所有数都小于堆顶的数据，这样即使所有数都遍历过去，堆中的数据都不会发生变化，建小堆的话堆顶的数据永远是堆中所有数据中最小的，遇到一个比堆顶数据大的数据就替换堆顶的数据，并向下调整堆中的数据，这样每次调整完之后，堆顶的数据都是堆中数据最小的，就这样我们遍历完所有的数据后，堆中的数据就是前K个最大的数据了，如果要是找前K个最小的数据的话建大堆并按此操作就可以了。

复杂度分析：

时间复杂度分析：建小堆的时间复杂度是O(K)，遍历一遍除了堆中其他的数据、每一次替换堆顶数据并向下调整的时间复杂度总共是log(K)(N-K)，所以总共的时间复杂度是log(K)(N-K)+K，化简并保留最高阶项得到的时间复杂度还是O(N*logK)，空间复杂度是我们建立K个数的堆所消耗的O(K)。

代码实现：

这里我们来实现一下思路二的代码：

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;
	}

	int randK = k;
	for (size_t i = 0; i < n; ++i)
	{
		int val = rand() % 100000;
		fprintf(fin, "%d\n", val);
	}

	fclose(fin);
	
	/************************************************************************/
	// 找topk
	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	//int minHeap[5];
	int* minHeap = malloc(sizeof(int)*k);
	if (minHeap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; ++i)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}

	// 建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(minHeap, k, i);
	}

	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			AdjustDown(minHeap, k, 0);
		}
	}
	for (int i = 0; i < k; ++i)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");
	fclose(fout);
}
int main()
{
	TestHeap5();

	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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73