【数据结构】什么是堆，如何使用无序数组生成一个堆？

---

一、堆的概念及其介绍

堆(Heap)是计算机科学中一类特殊的数据结构的统称，堆通常是一个可以被看做一棵完全二叉树的数组对象。如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆满足下列性质：

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

  • 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
  • 每个结点的值都小于或等于具左石孩子结点 的值，称为小顶堆。

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

结构图示

二、如何使用无序序列构建一个堆？

​ 如果有一组无序的数组，{50，10，90，30，70，40，80，60，20}，我们将它抽象为逻辑结构，z这时怎么将无序序列变成一个大堆或者小堆呢？

向上调整法

​ 从下标为1的位置开始，也就是图中10的位置，依次进行向上调整，每次将更小的换到上面，

题目中有个小问题，如何找到父节点？

• 父节点 = （子结点-1）/2

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
typedef int HeapDataType;

void swap(HeapDataType* a, HeapDataType* b)		//交换
{
	HeapDataType temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void Adjustup(HeapDataType* arr, int child)		//向上调整函数
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void CreateHeap(int* a, int n)			//使用无序数组创建堆
{
	for (int i = 1; i < n; i++)
	{
		Adjustup(a, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	int arr[] = { 50,10,90,30,70,40,80,60,20 };
	CreateHeap(arr, sizeof(arr) / sizeof(int));
}
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

向下调整法（更优）

​ 从非叶节点的最后一个数据的下标开始，每次取出孩子中较大或较小的数（看是大堆还是小堆）向下进行调整，由于每多一层，下层是上层的二倍，这种办法直接可以省略掉最后一层，也可以达到建堆的目的，所以这种办法为更优的办法。

由于需要向下调整，所以这种办法需要找到子节点，我们已经知道父结点的运算了，子结点就是父节点的逆运算。

• 子节点：父节点*2+1

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
typedef int HeapDataType;

void swap(HeapDataType* a, HeapDataType* b)		//交换
{
	HeapDataType temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void AdjustDown(HeapDataType* arr, int n, int parent)	//向下调整
{
	assert(arr);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child<n - 1 && arr[child] > arr[child + 1])
		{
			child = child + 1;
		}
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
		}
		parent = child;
		child = child * 2 + 1;
	}
}
void CreateHeap(int* a, int n)					//使用无序数组创建堆
{
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	int arr[] = { 50,10,90,30,70,40,80,60,20 };
	CreateHeap(arr, sizeof(arr) / sizeof(int));
}
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

三、C语言实现堆的基本操作

结构体创建与销毁

顺序存储方式实现堆采用顺序表进行存储。

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* arr;			
	int size;			//当前大小
	int capacity;		//当前容量上限
}Heap;

void HeapDestroy(Heap* ph)
{
	assert(ph);			
	free(ph->arr);
	ph->arr = NULL;
	ph->capacity = 0;
	ph->size = 0;
	free(ph);			//由于顺序表空间是申请堆空间的内存所以需要进行释放
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

获取堆顶数据与个数及堆的判空

HeapDataType HeapTop(Heap* ph) 
{
	assert(ph);
	return ph->arr[0];
}

int HeapSize(Heap* ph)
{
	assert(ph);
	return ph->size;
}

int HeapEmpty(Heap* ph)
{
	assert(ph);
	return ph->size == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

堆的插入与删除

插入时需要注意空间不足问题，如果空间不足，需要进行二次开辟空间，插入时直接插入到堆尾，然后利用上面写好的向上调整函数。

​ 删除时删掉堆顶数据，将堆底数据拿到堆顶，在进行向下调整，即可保证堆性质不变，依然保持原有的大/小堆。

void HeapPush(Heap* ph, HeapDataType x)
{
	assert(ph);
	if (ph->size == ph->capacity)
	{
		int newcapacity = ph->capacity == 0 ? 5 : ph->capacity * 2;
		HeapDataType* temp = (HeapDataType*)realloc(ph->arr, sizeof(int) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc: error");
			return;
		}
		ph->arr = temp;
		ph->capacity = newcapacity;
	}
	ph->arr[ph->size] = x;
	Adjustup(ph->arr, ph->size - 1);
	ph->size++;
}

void HeapPop(Heap* ph)
{
	assert(ph);
	assert(ph->arr);
	assert(!HeapEmpty(ph));
	swap(&ph->arr[ph->size - 1], &ph->arr[0]);
	ph->size--;
	AdjustDown(ph->arr, ph->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

源代码分享

//heap.h
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 


typedef int HeapDataType;
typedef struct Heap
{
	int* arr;
	int size;
	int capacity;
}Heap;

void HeapCreate(Heap* ph);
void HeapDestroy(Heap* ph);
void swap(HeapDataType* a, HeapDataType* b);
void Adjustup(HeapDataType* arr, int child);
void AdjustDown(HeapDataType* arr, int n, int parent);
void HeapPush(Heap* ph, HeapDataType x);
void HeapPop(Heap* ph);
HeapDataType HeapTop(Heap* ph);
int HeapSize(Heap* ph);
int HeapEmpty(Heap* ph);

//Heap.c
#include "Heap.h"

void HeapCreate(Heap* ph)
{
	assert(ph);
	ph->arr = NULL;
	ph->capacity = 0;
	ph->size = 0;

}

void HeapDestroy(Heap* ph)
{
	assert(ph);
	free(ph->arr);
	ph->arr = NULL;
	ph->capacity = 0;
	ph->size = 0;
	free(ph);
}

void swap(HeapDataType* a, HeapDataType* b)
{
	HeapDataType temp;
	temp = *a;
	*a = *b;
	*b = temp;
}


void Adjustup(HeapDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(HeapDataType* arr, int n, int parent)
{
	assert(arr);
	int child = parent * 2 + 1;
	while(child<n)
	{
		if (child<n-1&&arr[child] > arr[child + 1])
		{
			child = child + 1;
		}
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
		}
		parent = child;
		child = child * 2 + 1;
	}
}

void HeapPush(Heap* ph, HeapDataType x)
{
	assert(ph);
	if (ph->size == ph->capacity)
	{
		int newcapacity = ph->capacity == 0 ? 5 : ph->capacity * 2;
		HeapDataType* temp = (HeapDataType*)realloc(ph->arr, sizeof(int) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc: error");
			return;
		}
		ph->arr = temp;
		ph->capacity = newcapacity;
	}
	ph->arr[ph->size] = x;
	Adjustup(ph->arr, ph->size - 1);
	ph->size++;
}

void HeapPop(Heap* ph)
{
	assert(ph);
	assert(ph->arr);
	assert(!HeapEmpty(ph));
	swap(&ph->arr[ph->size - 1], &ph->arr[0]);
	ph->size--;
	AdjustDown(ph->arr, ph->size, 0);
}

HeapDataType HeapTop(Heap* ph) 
{
	assert(ph);
	return ph->arr[0];
}

int HeapSize(Heap* ph)
{
	assert(ph);
	return ph->size;
}

int HeapEmpty(Heap* ph)
{
	assert(ph);
	return ph->size == 0;
}

//test.c
void CreateHeap(int* a, int n)			//使用向上调整
{
	for (int i = 1; i < n; i++)
	{
		Adjustup(a, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
void CreateHeap(int* a, int n)		//使用向下调整
{
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	int arr[] = { 50,10,90,30,70,40,80,60,20 };
	CreateHeap(arr, sizeof(arr) / sizeof(int));
}
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
169
170

✨本文收录于数据结构理解与实现

当你喜欢一篇文章时，点赞、收藏和关注是最好的支持方式。如果你喜欢我的文章，请不要吝啬你的支持，点赞👍、收藏⭐和关注都是对我最好的鼓励。感谢你们的支持！