堆的实现
Heap.h 堆的管理及接口
|
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
|
#include<stdio.h>#include<stdlib.h>#include<assert.h>typedef int HPDataType;typedef struct Heap{ HPDataType* a; int size; int capacity;}Heap;//堆的向下调整算法void AdjustDown(HPDataType* a, int n, int root);//堆的向上调整算法void AdjustUp(HPDataType* a, int child);//堆的初始化void HeapInit(Heap* php, HPDataType* a,int n);//堆的销毁void HeapDestroy(Heap* php);//堆的插入void HeapPush(Heap* php, HPDataType x);//堆的删除void HeapPop(Heap* php);//堆里的数据个数int HeapSize(Heap* php);//判断堆是否为空int HeapEmpty(Heap* php);//取堆顶数据HPDataType HeapTop(Heap* php); |
Heap.c 堆各个接口功能的实现
• 堆的插入：将x插入下标为size的位置，++size然后使用向上调整算法调整
• 堆的删除(删栈顶数据)：将栈顶数据和下标为size-1位置的数据交换，然后–size,使用向下调整算法调整
|
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
|
#include "Heap.h"//堆向下调整算法//建小堆void AdjustDown(HPDataType* a, int n, int root){ int parent = root; int child = parent * 2 + 1; //孩子超过数组下标结束 while (child < n) { //child始终左右孩子中小的那个 if (a[child + 1] < a[child] && child + 1 <n)//防止没有右孩子 { ++child; } //小的往上浮，大的往下沉 if (a[child] < a[parent]) { int tem = a[parent]; a[parent] = a[child]; a[child] = tem; parent = child; child = parent * 2 + 1; } //中途child>parent则已满足小堆，直接break else { break; } }}//堆的向上调整算法//建小堆void AdjustUp(HPDataType* a, int child){ int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { int tem = a[parent]; a[parent] = a[child]; a[child] = tem; child = parent; parent = (child - 1) / 2; } else { break; } }}//堆的初始化void HeapInit(Heap* php, HPDataType* a, int n){ assert(php); assert(a); php->a = (HPDataType*)malloc(n * sizeof(HPDataType)); if (php->a == NULL) { printf("malloc fail\n"); exit(-1); } for (int i = 0; i < n; i++) { php->a[i] = a[i]; } //建堆 for (int i = (n - 2) / 2; i >= 0; --i) { AdjustDown(php->a, n, i); } php->capacity = n; php->size = n;}//堆的销毁void HeapDestroy(Heap* php){ assert(php); free(php->a); php->a = NULL; php->capacity = 0; php->size = 0;}//堆的插入void HeapPush(Heap* php, HPDataType x){ assert(php); if (php->size == php->capacity) { HPDataType* tem = (HPDataType*)realloc(php->a,php->capacity * 2 * sizeof(HPDataType)); if (tem == NULL) { printf("realloc fail\n"); exit(-1); } php->a = tem; php->capacity *= 2; } php->a[php->size] = x; ++php->size; AdjustUp(php->a,php->size - 1);}//堆的删除void HeapPop(Heap* php){ assert(php); assert(php->size > 0); HPDataType tem = php->a[php->size - 1]; php->a[php->size - 1] = php->a[0]; php->a[0] = tem; --php->size; AdjustDown(php->a, php->size, 0);}//堆里的数据个数int HeapSize(Heap* php){ assert(php); return php->size;}//判断堆是否为空//为空返回1，不为空返回0int HeapEmpty(Heap* php){ assert(php); return php->size == 0 ? 1 : 0;}//取堆顶数据HPDataType HeapTop(Heap* php){ assert(php); assert(php->size > 0); return php->a[0];} |
test.c测试
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include "Heap.h"void TestHeap(){ int arr[] = { 27, 28, 65, 25, 15, 34, 19, 49, 18, 37 }; Heap hp; HeapInit(&hp, arr, sizeof(arr)/sizeof(int)); while (!HeapEmpty(&hp)) { printf("%d ", HeapTop(&hp)); HeapPop(&hp); } printf("\n"); HeapDestroy(&hp);}int main(){ TestHeap(); return 0;} |
以上就是C++实现堆排序示例的详细内容，更多关于C++实现堆排序的资料请关注服务器之家其它相关文章！
原文链接：https://blog.csdn.net/weixin_50886514/article/details/114981407
