本文主要简述了数据结构堆的特性，以及使用C语言实现堆排序算法。
以下为我使用的C语言的运行和编译环境：
System Version : Ubuntu22.04.1
Linux kernel Version : 5.19.0
GCC Version : 11.3.0
STDC Version : 201710L
摘要： 堆的特性，堆排序的时间复杂度，堆算法的实现。
TODO 💤
1. 堆的性质
1.1. 定义
1.2. 特点
2. 实现堆排序算法
3. 使用C语言实现对象的堆排序算法
4. 源码
下述代码依赖于上篇文章数组
heap_ds.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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#ifndef _HEAP_DS_H_
#define _HEAP_DS_H_
#include "lang.h"
#include "args.h"
#include "typed.h"
EXTERN_C_BEGIN
typedef struct heap_ds_t heap_ds_t;
struct heap_ds_t {
void (*append)(size_t cnt, const void *data);
bool (*push)(const void *elem);
bool (*pop)(void *elem);
void *(*get0)(void);
void (*get1)(void *data);
void (*sort_nlogn)(void);
void (*sort_n)(void);
#ifndef get
#define get(...) MACRO_CAT(get, __VA_ARGS__)
#endif
size_t (*elem_cnt)(void);
size_t (*capacity)(void);
void (*destory)(void);
};
heap_ds_t *the_heap(heap_ds_t *public);
heap_ds_t *heap_ds_create(size_t capacity, size_t elem_size, elem_cmp cmp);
EXTERN_C_END
#endif
|
heap_ds.c
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "array_ds.h"
#include "heap_ds.h"
typedef struct _heap_ds_t _heap_ds_t;
struct _heap_ds_t {
heap_ds_t public;
elem_cmp cmp;
size_t index;
array_ds_t *pool;
};
static __thread _heap_ds_t *this = NULL;
#define HEAP_POOL the_array(this->pool)
#define HEAP_ELEM(_index) HEAP_POOL->get(_index)
#define HEAP_FIRST_INDEX (1)
#define HEAP_LAST_INDEX (this->index)
#define HEAP_BACK_INDEX (0)
#define HEAP_ELEM_PARENT(_index) (_index/ 2)
#define HEAP_ELEM_LCHILD(_index) (2 * _index)
#define HEAP_ELEM_RCHILD(_index) (2 * _index + 1)
static size_t heap_elem_cnt(void)
{
return HEAP_LAST_INDEX - HEAP_FIRST_INDEX;
}
static size_t heap_capacity(void)
{
return HEAP_POOL->capacity() - 1;
}
static void shiftup(size_t hole)
{
size_t parent = HEAP_ELEM_PARENT(hole);
HEAP_POOL->set(HEAP_BACK_INDEX, HEAP_ELEM(hole));
while (hole > 0 && this->cmp(HEAP_ELEM(HEAP_BACK_INDEX), HEAP_ELEM(parent))) {
HEAP_POOL->set(hole, HEAP_ELEM(parent));
hole = parent;
parent = HEAP_ELEM_PARENT(hole);
}
HEAP_POOL->set(hole, HEAP_ELEM(HEAP_BACK_INDEX));
}
static void shiftdown(size_t hole)
{
size_t lchild = HEAP_ELEM_LCHILD(hole);
size_t rchild = HEAP_ELEM_RCHILD(hole);
size_t child = lchild;
if ( lchild > HEAP_LAST_INDEX - 1) return;
HEAP_POOL->set(HEAP_BACK_INDEX, HEAP_ELEM(hole));
if ( lchild == HEAP_LAST_INDEX - 1) {
if (this->cmp(HEAP_ELEM(child), HEAP_ELEM(HEAP_BACK_INDEX))) {
HEAP_POOL->set(hole, HEAP_ELEM(child));
hole = child;
lchild = HEAP_ELEM_LCHILD(hole);
rchild = HEAP_ELEM_RCHILD(hole);
}
}
while (rchild <= HEAP_LAST_INDEX - 1) {
if (this->cmp(HEAP_ELEM(lchild), HEAP_ELEM(rchild)))
child = lchild;
else
child = rchild;
if (this->cmp(HEAP_ELEM(child), HEAP_ELEM(HEAP_BACK_INDEX))) {
HEAP_POOL->set(hole, HEAP_ELEM(child));
hole = child;
lchild = HEAP_ELEM_LCHILD(hole);
rchild = HEAP_ELEM_RCHILD(hole);
}
else {
break;
}
}
HEAP_POOL->set(hole, HEAP_ELEM(HEAP_BACK_INDEX));
}
static void heap_sort_up(void)
{
for(size_t hole = HEAP_FIRST_INDEX + 1; hole <= heap_elem_cnt(); hole++)
{
shiftup(hole);
}
}
static void heap_sort_down(void)
{
for(size_t hole = HEAP_ELEM_PARENT(heap_elem_cnt()); hole >= HEAP_FIRST_INDEX; hole--)
{
shiftdown(hole);
}
}
static void heap_append(size_t cnt, const void *data)
{
HEAP_POOL->insert(HEAP_LAST_INDEX, cnt, data);
HEAP_LAST_INDEX += cnt;
heap_sort_down();
}
static bool heap_push(const void *elem)
{
if (HEAP_LAST_INDEX == HEAP_POOL->capacity()) {
return false;
}
HEAP_POOL->set(HEAP_LAST_INDEX, elem);
shiftup(HEAP_LAST_INDEX);
HEAP_LAST_INDEX++;
return true;
}
static bool heap_pop(void *elem)
{
if (HEAP_LAST_INDEX == HEAP_FIRST_INDEX) {
return false;
}
HEAP_POOL->get(HEAP_FIRST_INDEX, elem);
HEAP_POOL->set(HEAP_FIRST_INDEX, HEAP_ELEM(HEAP_LAST_INDEX));
HEAP_LAST_INDEX--;
shiftdown(HEAP_FIRST_INDEX);
return true;
}
static void *heap_get0(void)
{
return HEAP_ELEM(HEAP_FIRST_INDEX);
}
static void heap_get1(void *data)
{
HEAP_POOL->get(HEAP_FIRST_INDEX, heap_elem_cnt(), data);
}
static void destory(void)
{
if(!this) return;
if(this->pool) HEAP_POOL->destory();
free(this);
this = NULL;
return;
}
heap_ds_t *the_heap(heap_ds_t *public)
{
this = (_heap_ds_t *)public;
return &this->public;
}
heap_ds_t *heap_ds_create(size_t capacity, size_t elem_size, elem_cmp cmp)
{
_heap_ds_t *_this = (_heap_ds_t *)malloc(sizeof(_heap_ds_t));
_this->public.append = heap_append;
_this->public.push = heap_push;
_this->public.pop = heap_pop;
_this->public.get0 = heap_get0;
_this->public.get1 = heap_get1;
_this->public.sort_nlogn= heap_sort_up;
_this->public.sort_n = heap_sort_down;
_this->public.elem_cnt = heap_elem_cnt;
_this->public.capacity = heap_capacity;
_this->public.destory = destory;
_this->pool = array_ds_create(capacity + 1, elem_size);
_this->cmp = cmp;
_this->index = HEAP_FIRST_INDEX;
return &_this->public;
}
|
微信
支付宝
