堆的实现
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，不为空返回0
int 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