-
Notifications
You must be signed in to change notification settings - Fork 0
/
min-heap.c
250 lines (207 loc) · 6.35 KB
/
min-heap.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
242
243
244
245
246
247
248
249
250
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
/**
* A binary min heap implemented as an implicit data structure. Keys are stored
* as an array, and parent-child relationships will be determined by relative
* positions within the array: for an element at given index `i`, its children
* will be located at `2 * i + 1` and `2 * i + 2`, and its parent will be
* located at `(i - 1) / 2` (using integer division). All parent nodes will be
* less than or equal to their child nodes.
*/
typedef struct MinHeap {
int maxSize;
int length;
int array[];
} MinHeap;
/**
* Constructs a new instance of a min heap and returns a pointer to it. (Make
* sure to `free` the pointer once you're finished with it.)
*/
MinHeap *newMinHeap(int maxSize) {
if (maxSize < 1) {
printf("Error: maximum size must be positive.\n");
return NULL;
}
MinHeap *ptr = malloc(sizeof(MinHeap) + maxSize * sizeof(int));
ptr->maxSize = maxSize;
ptr->length = 0;
return ptr;
}
/** Returns the number of values in a min heap. */
int length(MinHeap *heap) { return heap->length; }
/** Returns whether or not a min heap is empty. */
bool isEmpty(MinHeap *heap) { return length(heap) == 0; }
/** Returns whether or not a min heap is full. */
bool isFull(MinHeap *heap) { return length(heap) == heap->maxSize; }
/**
* Adds a value to a min heap, maintaining the heap property.
*
* @param heap A pointer to the min heap.
* @param value The value to add.
* @return `0` if the value was successfully added, `1` if the min heap was
* already at maximum capacity (stack overflow).
*/
int push(MinHeap *heap, int value) {
if (isFull(heap)) {
printf("Error: stack overflow: heap is already at maximum capacity.\n");
return 1;
}
int currentIndex = heap->length;
int parentIndex = (currentIndex - 1) / 2;
while (currentIndex > 0 && value < heap->array[parentIndex]) {
// Switch with parent
heap->array[currentIndex] = heap->array[parentIndex];
currentIndex = parentIndex;
parentIndex = (currentIndex - 1) / 2;
}
heap->array[currentIndex] = value;
heap->length++;
return 0;
}
/**
* Removes and returns the least value in a min heap, reordering the internal
* array to maintain the heap property.
*
* @param heap A pointer to the min heap.
* @return A pointer to an integer denoting the value removed, or `NULL` if the
* min heap was already empty.
*/
int *pop(MinHeap *heap) {
if (isEmpty(heap))
return NULL;
// Save return value
int min = heap->array[0];
heap->length--;
if (heap->length == 0) {
int *ptr = &min;
return ptr;
}
// Rebalance the heap by moving the last element into the root position, then
// continuing to swap it with its least-valued child until it is greater than
// both children or it reaches the last level of the tree
int currentIdx = 0;
int child1Idx = 2 * currentIdx + 1;
int child2Idx = 2 * currentIdx + 2;
int value = heap->array[heap->length];
while ((child1Idx < heap->length && value > heap->array[child1Idx]) ||
(child2Idx < heap->length && value > heap->array[child2Idx])) {
if (child2Idx >= heap->length ||
heap->array[child1Idx] < heap->array[child2Idx]) {
// Swap with child 1
heap->array[currentIdx] = heap->array[child1Idx];
currentIdx = child1Idx;
} else {
// Swap with child 2
heap->array[currentIdx] = heap->array[child2Idx];
currentIdx = child2Idx;
}
child1Idx = 2 * currentIdx + 1;
child2Idx = 2 * currentIdx + 2;
}
heap->array[currentIdx] = value;
int *ptr = &min;
return ptr;
}
/**
* Returns an array of all values currently stored in a min heap (in the order
* of the internal data structure).
*
* @param heap A pointer to the min heap.
* @return `NULL` if the heap is currently empty; otherwise, a pointer to the
* first element of the array of values. Take care not to attempt to access
* array members at indices of `heap->length` or greater, as this will produce
* garbage values.
*/
int *print(MinHeap *heap) {
if (isEmpty(heap))
return NULL;
int array[heap->length];
for (int i = 0; i < heap->length; i++) {
array[i] = heap->array[i];
}
int *ptr = array;
return ptr;
}
/** Clears the contents of a min heap. */
void clear(MinHeap *heap) { heap->length = 0; }
/** Creates a deep clone of a min heap. */
MinHeap *clone(MinHeap *original) {
MinHeap *clone = newMinHeap(original->maxSize);
clone->length = original->length;
for (int i = 0; i < original->length; i++) {
clone->array[i] = original->array[i];
}
return clone;
}
/**
* Returns a pointer to an array of all values in a min heap ordered from least
* to greatest.
*
* @param heap A pointer to the min heap.
* @return `NULL` if the heap is currently empty; otherwise, a pointer to the
* first element of the array of values. Take care not to attempt to access
* array members at indices of `heap->length` or greater, as this will produce
* garbage values.
*/
int *sort(MinHeap *heap) {
if (isEmpty(heap))
return NULL;
MinHeap *copy = clone(heap);
int sorted[heap->length];
for (int i = 0; i < heap->length; i++) {
sorted[i] = *pop(copy);
}
free(copy);
int *ptr = sorted;
return ptr;
}
int main() {
assert(newMinHeap(0) == NULL);
MinHeap *h = newMinHeap(10);
assert(isEmpty(h));
assert(length(h) == 0);
assert(pop(h) == NULL);
int minValue = INT_MAX;
for (int i = 0; i < 5; i++) {
int value = rand() % 100;
if (value < minValue)
minValue = value;
assert(push(h, value) == 0);
}
assert(length(h) == 5);
assert(!isEmpty(h));
assert(!isFull(h));
for (int i = 0; i < 5; i++) {
int value = rand() % 100;
if (value < minValue)
minValue = value;
assert(push(h, value) == 0);
}
assert(length(h) == 10);
assert(isFull(h));
int *unsorted = print(h);
assert(unsorted[0] == minValue);
// Test heap property
for (int i = 1; i < 10; i++) {
assert(unsorted[i] >= unsorted[(i - 1) / 2]);
}
int *sorted = sort(h);
assert(sorted[0] == minValue);
// Test sorting
for (int i = 1; i < 10; i++) {
assert(sorted[i] >= sorted[i - 1]);
}
assert(push(h, 1) == 1);
assert(*pop(h) == minValue);
clear(h);
assert(length(h) == 0);
assert(isEmpty(h));
assert(print(h) == NULL);
assert(sort(h) == NULL);
free(h);
printf("All tests passed successfully.\n");
return 0;
}