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
|
/*
* Binary heap
*
* (c) 2012 Ondrej Filip <feela@network.cz>
*
* This software may be freely distributed and used according to the terms
* of the GNU Lesser General Public License.
*/
/***
* Introduction
* ------------
*
* Binary heap is a simple data structure, which for example supports efficient insertions, deletions
* and access to the minimal inserted item. We define several macros for such operations.
* Note that because of simplicity of heaps, we have decided to define direct macros instead
* of a <<generic:,macro generator>> as for several other data structures in the Libucw.
*
* A heap is represented by a number of elements and by an array of values. Beware that we
* index this array from one, not from zero as do the standard C arrays.
*
* Most macros use these parameters:
*
* - @num - a variable (signed or unsigned integer) with the number of elements
* - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused
*
* A valid heap must follow these rules:
*
* - `num >= 0`
* - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
*
* The first element `heap[1]` is always lower or equal to all other elements.
***/
#include <string.h>
#include <stdlib.h>
#include "contrib/ucw/heap.h"
static inline void heap_swap(heap_val_t **e1, heap_val_t **e2)
{
if (e1 == e2) return; /* Stack tmp should be faster than tmpelem. */
heap_val_t *tmp = *e1; /* Even faster than 2-XOR nowadays. */
*e1 = *e2;
*e2 = tmp;
int pos = (*e1)->pos;
(*e1)->pos = (*e2)->pos;
(*e2)->pos = pos;
}
int heap_init(struct heap *h, int (*cmp)(void *, void *), int init_size)
{
int isize = init_size ? init_size : INITIAL_HEAP_SIZE;
h->num = 0;
h->max_size = isize;
h->cmp = cmp;
h->data = malloc((isize + 1) * sizeof(heap_val_t*)); /* Temp element unused. */
return h->data ? 1 : 0;
}
void heap_deinit(struct heap *h)
{
free(h->data);
memset(h, 0, sizeof(*h));
}
static inline void _heap_bubble_down(struct heap *h, int e)
{
int e1;
for (;;) {
e1 = 2 * e;
if (e1 > h->num) break;
if ((h->cmp(*HELEMENT(h, e), *HELEMENT(h, e1)) < 0) &&
(e1 == h->num || (h->cmp(*HELEMENT(h, e), *HELEMENT(h, e1 + 1)) < 0))) break;
if ((e1 != h->num) && (h->cmp(*HELEMENT(h, e1 + 1), *HELEMENT(h, e1)) < 0)) e1++;
heap_swap(HELEMENT(h, e), HELEMENT(h, e1));
e = e1;
}
}
static inline void _heap_bubble_up(struct heap *h, int e)
{
int e1;
while (e > 1) {
e1 = e / 2;
if (h->cmp(*HELEMENT(h, e1), *HELEMENT(h, e)) < 0) break;
heap_swap(HELEMENT(h, e), HELEMENT(h, e1));
e = e1;
}
}
void heap_replace(struct heap *h, int pos, heap_val_t *e)
{
*HELEMENT(h, pos) = e;
e->pos = pos;
if (pos == 1 || h->cmp(*HELEMENT(h, pos / 2), e) < 0) {
_heap_bubble_down(h, pos);
} else {
_heap_bubble_up(h, pos);
}
}
void heap_delmin(struct heap *h)
{
if (h->num == 0) return;
if (h->num > 1) {
heap_swap(HHEAD(h), HELEMENT(h, h->num));
}
(*HELEMENT(h, h->num))->pos = 0;
h->num--;
_heap_bubble_down(h, 1);
}
int heap_insert(struct heap *h, heap_val_t *e)
{
if (h->num == h->max_size) {
h->max_size = h->max_size * HEAP_INCREASE_STEP;
h->data = realloc(h->data, (h->max_size + 1) * sizeof(heap_val_t*));
if (!h->data) {
return 0;
}
}
h->num++;
*HELEMENT(h, h->num) = e;
e->pos = h->num;
_heap_bubble_up(h, h->num);
return 1;
}
int heap_find(struct heap *h, heap_val_t *elm)
{
return ((struct heap_val *) elm)->pos;
}
void heap_delete(struct heap *h, int e)
{
heap_swap(HELEMENT(h, e), HELEMENT(h, h->num));
(*HELEMENT(h, h->num))->pos = 0;
h->num--;
if (h->cmp(*HELEMENT(h, e), *HELEMENT(h, h->num + 1)) < 0) {
_heap_bubble_up(h, e);
} else {
_heap_bubble_down(h, e);
}
if ((h->num > INITIAL_HEAP_SIZE) && (h->num < h->max_size / HEAP_DECREASE_THRESHOLD)) {
h->max_size = h->max_size / HEAP_INCREASE_STEP;
h->data = realloc(h->data, (h->max_size + 1) * sizeof(heap_val_t*));
}
}
|
