【数据结构】堆的向上调整和向下调整以及相关方法

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃

文章目录

• 一、堆的概念
• 二、堆的性质
• 三、堆的分类
• • 1.大根堆
  • 2.小根堆
• 四、说明
• 五、堆的结构
• 🚩六、堆的向上调整
• • 1.图示
  • 2.代码实现
  • ⌚️3.时间复杂度分析
• 📌七、堆的向下调整
• • 1.思路：
  • 2.代码实现
  • ⌚️3.时间复杂度分析
• 八、删除根
• • 1.思路：
  • 2.代码实现
  • ⌚️3.时间复杂度分析
• 九、创建堆
• • 1.思路：
  • 2.代码实现
• 十、所有方法实现汇总

一、堆的概念

堆(Heap)是计算机科学中一类特殊的数据结构的统称。如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。除了最后一层以外上面的节点但是非空的，最后一层节点是从左到右依次排布的）

二、堆的性质

🔸 非线性，完全二叉树。适合用数组存储。
🔸堆是无序的，也就是左右可以互换
🔸最值总在 0 号位
根据这个特点我们就可以做很多事情，比如TopK问题 (在一堆数据里面找到前 K 个最大 / 最小的数).
比如点餐软件中有上千家店铺，我想选出该地区好评最多的十家川菜店，我们不用对所有数据排序，只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。

三、堆的分类

1.大根堆 2.小根堆

1.大根堆

定义：树中的任意一个双亲节点都大于等于孩子节点。

2.小根堆

定义：树中的任意一个双亲节点都小于等于孩子节点。

四、说明

以下的方法均以小堆来推理，如果想实现大堆，则修改【<】符号等方式实现。

五、堆的结构

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

🚩六、堆的向上调整

向上调整的前提是，调整位置之前必须是堆。如果目的是调成小堆，则要保证调整位置之前是小堆；如果目的是调成大堆，则要保证调整位置之前是大堆。

1.图示

2.代码实现

//向上调整
void AdjustUp(HPDataType* a, int child)
{
	//传入数组，child为孩子节点下标
	int parent = (child - 1) / 2;
	//当一直交换到根，停止
	while (child>0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			return;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

⌚️3.时间复杂度分析

时间复杂度：O（logN）
最坏情况：调整到根;
最好情况：不用调整，

📌七、堆的向下调整

向下调整的前提是，左右子树必须是小堆或者大堆。

1.思路：

如图：
此案例是要调整根节点40开始向下调整，首先确保根节点的左右子树是小堆（由图得成立）。
1.parent的两个孩子进行比较，选出小的。
2.进行交换
3.child>n结束

2.代码实现

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//一直交换到数的最后，也就是数组的最后一个位置
	while (parent<n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			// 继续往下调整
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			return;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

⌚️3.时间复杂度分析

时间复杂度：O（logN）
最坏情况：调整到根;
最好情况：不用调整，

八、删除根

1.思路：

1.先将根与最后一个节点交换，
2.删除最后一个节点；
3.进行向下调整。

2.代码实现

void HeapPop(HP* p)
{
	assert(p);
	assert(p->size > 0);

	Swap(&p->a[0], &p->a[p->size - 1]);
	--p->size;

	AdjustDown(p->a, p->size, 0);
}
1
2
3
4
5
6
7
8
9
10

⌚️3.时间复杂度分析

时间复杂度：O:N(logN)

九、创建堆

创建堆的思路可以通过向上调整，也可通过向下调整。这里讲通过向上调整建立堆。
由于我的AdjustUp函数是用来调整小堆的，所以，这里创建的也是小堆。

1.思路：

传入参数
a：数组，n：是数组元素个数
1.为p->a开辟n个空间；
2.利用memcpy函数，把数组a复制到p->a中
3.在使用AdjustUp调整，从1-n-1逐步向下延伸；

2.代码实现

//建立小堆
void HeapInitArray(HP* p, int* a, int n)
{
	//a：数组，n：是数组元素个数
	assert(p);
	assert(a);

	p->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (p->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	p->size = n;
	p->capacity = n;
	//把传入数组a复制到p->a中
	memcpy(p->a, a, sizeof(HPDataType) * n);

	// 向上调整，调整成一个小堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(p->a, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

十、所有方法实现汇总

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

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

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

//插入数据
void HeapPush(HP* p, HPDataType x)
{
	//从最后一个位置插入
	assert(p);
	//扩容
	if (p->capacity == p->size)
	{
		//如果刚开始数组为空，就开辟4个空间。如果不为空，以后每次扩大2倍。
		int newcapacity = p->capacity==0 ? 4 : p->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(p->a, sizeof(HPDataType) * p->capacity);
		if (tmp == NULL)
		{
			perror("realloc fial\n");
			exit(-1);
		}
		p->a = tmp;
		p->capacity = newcapacity;
	}
	p->a[p->size] = x;
	p->size++;
		AdjustUp(p->a, p->size-1);
}

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

//向上调整
void AdjustUp(HPDataType* a, int child)
{
	//传入数组，child为孩子节点下标
	int parent = (child - 1) / 2;
	//当一直交换到根，停止
	while (child>0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			return;
	}
}

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//一直交换到数的最后，也就是数组的最后一个位置
	while (parent<n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			// 继续往下调整
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			return;
		}
	}
}


//打印二叉树
void HeapPrint(HP* php)
{
	assert(php);

	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}


//建立小堆
void HeapInitArray(HP* p, int* a, int n)
{
	//a：数组，n：是数组元素个数
	assert(p);
	assert(a);

	p->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (p->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	p->size = n;
	p->capacity = n;
	//把传入数组a复制到p->a中
	memcpy(p->a, a, sizeof(HPDataType) * n);

	// 向上调整，调整成一个小堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(p->a, i);
	}
}

//删除根
void HeapPop(HP* p)
{
	assert(p);
	assert(p->size > 0);

	Swap(&p->a[0], &p->a[p->size - 1]);
	--p->size;

	AdjustDown(p->a, p->size, 0);
}
//获取根
HPDataType HeapTop(HP* p)
{
	assert(p);
	assert(p->size > 0);

	return p->a[0];
}

//判空
bool HeapEmpty(HP* p)
{
	assert(p);

	return p->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