-
Notifications
You must be signed in to change notification settings - Fork 0
/
generic_heap.c
91 lines (77 loc) · 1.77 KB
/
generic_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
#ifndef GENERIC_HEAP_C
#define GENERIC_HEAP_C
//Non-generic helper functions and includes are include-guarded to prevent duplication.
#include <assert.h>
static int parent_index(int i)
{
return (i - 1) / 2;
}
//Left Child Index
static int lci(int i)
{
return i*2 + 1;
}
//Right Child Index
static int rci(int i)
{
return i*2 + 2;
}
#endif
HEAP GENERIC(new_heap)(GENERIC_TYPE arr[], int len)
{
return (HEAP) {
._arr = arr,
.max = len,
.len = 0
};
}
GENERIC_TYPE GENERIC(peek)(HEAP *ph)
{
if (ph->len < 1)
assert(0);
return ph->_arr[0];
}
static void GENERIC(swap)(GENERIC_TYPE *p1, GENERIC_TYPE *p2) {
GENERIC_TYPE tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
static void GENERIC(sift)(HEAP *ph, int i, int (*compare)(GENERIC_TYPE, GENERIC_TYPE))
{
int pi = parent_index(i);
if (compare(ph->_arr[i], ph->_arr[pi]) > 0) {
GENERIC(swap)(&ph->_arr[i], &ph->_arr[pi]);
GENERIC(sift)(ph, pi, compare);
}
}
static void GENERIC(sift_down)(HEAP *ph, int i, int (*compare)(GENERIC_TYPE, GENERIC_TYPE))
{
int l = lci(i);
int r = rci(i);
int mi = i;
if (l <= ph->len && compare(ph->_arr[l], ph->_arr[mi]) > 0)
mi = l;
if (r <= ph->len && compare(ph->_arr[r], ph->_arr[mi]) > 0)
mi = r;
if (mi != i) {
GENERIC(swap)(&ph->_arr[i], &ph->_arr[mi]);
GENERIC(sift_down)(ph, mi, compare);
}
}
int GENERIC(heap_add)(HEAP *ph, GENERIC_TYPE v, int (*compare)(GENERIC_TYPE, GENERIC_TYPE))
{
if (ph->len >= ph->max)
return -1;
ph->_arr[(ph->len)++] = v;
GENERIC(sift)(ph, (ph->len - 1), compare);
return 0;
}
GENERIC_TYPE GENERIC(heap_rem)(HEAP *ph, int (*compare)(GENERIC_TYPE, GENERIC_TYPE))
{
if (ph->len < 1)
assert(0); //Great error handling
GENERIC_TYPE root = GENERIC(peek)(ph);
ph->_arr[0] = ph->_arr[--(ph->len)];
GENERIC(sift_down)(ph, 0, compare);
return root;
}