堆的概念
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象，即是一种顺序储存结构的完全二叉树。
提示：完全二叉树
完全二叉树：对一棵深度为k、有n个结点二叉树编号后，各节点的编号与深度为k的满二叉树相同位置的结点的编号相同，这颗二叉树就被称为完全二叉树。[2]
堆的性质
- 堆中某个结点的值总是不大于或不小于其父结点的值
- 堆总是一棵完全二叉树
- 除了根结点和最后一个左子结点可以没有兄弟结点，其他结点必须有兄弟结点
最大堆最小堆
-
最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
-
最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。
代码
定义
有限数组形式
|
1
|
int Heap[1024]; //顺序结构的二叉树 |
若某结点编号为i，且存在左儿子和右儿子，则他们分别对应
|
1
2
|
Heap[i*2+1]; //左儿子Heap[i*2+2]; //右儿子 |
其父节点
|
1
|
Heap[i/2]; //i的父节点 |
动态数组形式
在项目开发中，经常以动态数组形式出现，在本文主要对这种形式进行介绍
|
1
2
3
4
5
6
7
8
9
|
//默认容量#define DEFAULT_CAPCITY 128typedef struct _Heap{ int *arr; //储存元素的动态数组 int size; //元素个数 int capacity; //当前存储的容量 }Heap; |
操作
只使用InitHeap()函数进行初始化即可，AdjustDown()与BuildHeap()仅为堆建立时的内部调用
向下调整结点
- 以创建最大堆为例
- 将“判断最大子结点是否大于当前父结点”处的>=改为<=即可创建最小堆
|
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
|
//向下调整，将当前结点与其子结点调整为最大堆//用static修饰禁止外部调用static void AdjustDown(Heap& heap, int index){ int cur = heap.arr[index]; //当前待调整结点 int parent, child; /* 判断是否存在子结点大于当前结点。 若不存在，堆是平衡的，则不调整； 若存在，则与最大子结点与之交换，交换后该子节点若还有子结点，则以此方法继续调整。 */ for (parent = index; (parent * 2 + 1) < heap.size; parent = child) { child = parent * 2 + 1; //左子结点 //取两个子结点中最大节点,(child+1)<heap.size防止越界 if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1]))) child++; //判断最大子结点是否大于当前父结点 if (cur >= heap.arr[child]) //将此处的>=改成<=可构建最小堆 { //不大于，不需要调整 break; } else { //大于，则交换 heap.arr[parent] = heap.arr[child]; heap.arr[child] = cur; } }} |
建立堆
|
1
2
3
4
5
6
7
8
9
10
|
//建立堆，用static修饰禁止外部调用static void BuildHeap(Heap& heap){ int i; //从倒数第二层开始调整（若只有一层则从该层开始） for (i = heap.size / 2 - 1; i >= 0; i--) { AdjustDown(heap, 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
25
26
27
|
//初始化堆//参数：被初始化的堆，存放初始数据的数组， 数组大小bool InitHeap(Heap &heap, int *orginal, int size){ //若容量大于size，则使用默认量，否则为size int capacity = DEFAULT_CAPCITY>size?DEFAULT_CAPCITY:size; heap.arr = new int[capacity]; //分配内存，类型根据实际需要可修改 if(!heap.arr) return false; //内存分配失败则返回False heap.capacity = capacity; //容量 heap.size = 0; //元素个数置为0 //若存在原始数组则构建堆 if(size>0) { /* 内存拷贝，将orginal的元素拷贝到堆数组arr中 size*sizeof(int)为元素所占内存空间大小 */ memcpy(heap.arr,orginal, size*sizeof(int)); heap.size = size; //调整大小 BuildHeap(heap); //建堆 } return true;} |
打印堆
- 实际上是一个层序遍历[4]
|
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
|
//以树状的形式打印堆void PrintHeapAsTreeStyle(Heap hp){ queue<int> que; int r = 0; que.push(r); queue<int> temp; while (!que.empty()) { r = que.front(); que.pop(); if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1); if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2); if (que.empty()) { cout << hp.arr[r] << endl; que = temp; temp = queue<int>(); } else cout << hp.arr[r] << " "; }} |
测试
main函数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int main(){ Heap hp; int vals[] = { 1,2,3,87,93,82,92,86,95 }; if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0]))) { fprintf(stderr, "初始化堆失败！\n"); exit(-1); } PrintHeapAsTreeStyle(hp); return 0;} |
结果
|
1
2
3
4
|
9593 9287 1 82 386 2 |
完整代码
|
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
|
#include <iostream>#include <queue>using namespace std;//默认容量#define DEFAULT_CAPCITY 128typedef struct _Heap { int* arr; int size; int capacity;}Heap;//向下调整，将当前结点与其子结点调整为最大堆static void AdjustDown(Heap& heap, int index){ int cur = heap.arr[index]; //当前待调整结点 int parent, child; /* 判断是否存在子结点大于当前结点。 若不存在，堆是平衡的，则不调整； 若存在，则与最大子结点与之交换，交换后该子节点若还有子结点，则以此方法继续调整。 */ for (parent = index; (parent * 2 + 1) < heap.size; parent = child) { child = parent * 2 + 1; //左子结点 //取两个子结点中最大节点,(child+1)<heap.size防止越界 if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1]))) child++; //判断最大子结点是否大于当前父结点 if (cur >= heap.arr[child]) //将此处的>=改成<=可构建最小堆 { //不大于，不需要调整 break; } else { //大于，则交换 heap.arr[parent] = heap.arr[child]; heap.arr[child] = cur; } }}//建立堆，用static修饰禁止外部调用static void BuildHeap(Heap& heap){ int i; //从倒数第二层开始调整（若只有一层则从该层开始） for (i = heap.size / 2 - 1; i >= 0; i--) { AdjustDown(heap, i); }}//初始化堆//参数：被初始化的堆，存放初始数据的数组， 数组大小bool InitHeap(Heap& heap, int* orginal, int size){ //若容量大于size，则使用默认量，否则为size int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size; heap.arr = new int[capacity]; //分配内存，类型根据实际需要可修改 if (!heap.arr) return false; //内存分配失败则返回False heap.capacity = capacity; //容量 heap.size = 0; //元素个数置为0 //若存在原始数组则构建堆 if (size > 0) { /* 内存拷贝，将orginal的元素拷贝到堆数组arr中 size*sizeof(int)为元素所占内存空间大小 */ memcpy(heap.arr, orginal, size * sizeof(int)); heap.size = size; //调整大小 BuildHeap(heap); //建堆 } return true;}//以树状的形式打印堆void PrintHeapAsTreeStyle(Heap hp){ queue<int> que; int r = 0; que.push(r); queue<int> temp; while (!que.empty()) { r = que.front(); que.pop(); if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1); if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2); if (que.empty()) { cout << hp.arr[r] << endl; que = temp; temp = queue<int>(); } else cout << hp.arr[r] << " "; }}int main(){ Heap hp; int vals[] = { 1,2,3,87,93,82,92,86,95 }; if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0]))) { fprintf(stderr, "初始化堆失败！\n"); exit(-1); } PrintHeapAsTreeStyle(hp); return 0;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://www.cnblogs.com/cairbin/p/16122303.html
