堆的實(shí)現(xiàn)
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;//堆的向下調(diào)整算法void AdjustDown(HPDataType* a, int n, int root);//堆的向上調(diào)整算法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);//堆里的數(shù)據(jù)個(gè)數(shù)int HeapSize(Heap* php);//判斷堆是否為空int HeapEmpty(Heap* php);//取堆頂數(shù)據(jù)HPDataType HeapTop(Heap* php); |
Heap.c 堆各個(gè)接口功能的實(shí)現(xiàn)
• 堆的插入：將x插入下標(biāo)為size的位置，++size然后使用向上調(diào)整算法調(diào)整
• 堆的刪除(刪棧頂數(shù)據(jù))：將棧頂數(shù)據(jù)和下標(biāo)為size-1位置的數(shù)據(jù)交換，然后–size,使用向下調(diào)整算法調(diào)整
|
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"//堆向下調(diào)整算法//建小堆void AdjustDown(HPDataType* a, int n, int root){ int parent = root; int child = parent * 2 + 1; //孩子超過數(shù)組下標(biāo)結(jié)束 while (child < n) { //child始終左右孩子中小的那個(gè) 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; } }}//堆的向上調(diào)整算法//建小堆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);}//堆里的數(shù)據(jù)個(gè)數(shù)int HeapSize(Heap* php){ assert(php); return php->size;}//判斷堆是否為空//為空返回1，不為空返回0int HeapEmpty(Heap* php){ assert(php); return php->size == 0 ? 1 : 0;}//取堆頂數(shù)據(jù)HPDataType HeapTop(Heap* php){ assert(php); assert(php->size > 0); return php->a[0];} |
test.c測(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++實(shí)現(xiàn)堆排序示例的詳細(xì)內(nèi)容，更多關(guān)于C++實(shí)現(xiàn)堆排序的資料請(qǐng)關(guān)注服務(wù)器之家其它相關(guān)文章！
原文鏈接：https://blog.csdn.net/weixin_50886514/article/details/114981407
