1 |
greg |
2.2 |
#ifndef lint |
2 |
|
|
static const char RCSid[] = "$Id$"; |
3 |
|
|
#endif |
4 |
greg |
2.1 |
#include <stdio.h> |
5 |
|
|
#include <stdlib.h> |
6 |
|
|
|
7 |
|
|
#include "maxheap.h" |
8 |
|
|
|
9 |
|
|
|
10 |
|
|
static int resize_heap(maxHeap* hp,int sz) |
11 |
|
|
{ |
12 |
|
|
int i; |
13 |
|
|
|
14 |
|
|
if (sz == hp->cap) |
15 |
|
|
return 1; |
16 |
|
|
hp->heap = (heapElem*) realloc(hp->heap,sz*sizeof(heapElem)); |
17 |
|
|
if (!hp->heap) |
18 |
|
|
return 0; |
19 |
|
|
for(i=hp->size;i<sz;i++) { |
20 |
|
|
hp->heap[i].entity = NULL; |
21 |
|
|
hp->heap[i].key = -HUGE; |
22 |
|
|
} |
23 |
|
|
hp->cap = sz; |
24 |
|
|
if (sz < hp->size) { |
25 |
|
|
hp->size = sz; |
26 |
|
|
hp->state = HP_INVALID; |
27 |
|
|
} |
28 |
|
|
if (sz == 0) { |
29 |
|
|
hp->heap = NULL; |
30 |
|
|
hp->state = HP_BUILD; |
31 |
|
|
} |
32 |
|
|
return 1; |
33 |
|
|
} |
34 |
|
|
|
35 |
|
|
int mheap_init(maxHeap* hp) |
36 |
|
|
{ |
37 |
|
|
hp->size = 0; |
38 |
|
|
hp->cap = 0; |
39 |
|
|
hp->heap = NULL; |
40 |
|
|
hp->state = HP_BUILD; |
41 |
|
|
return resize_heap(hp,HP_STARTCAP); |
42 |
|
|
} |
43 |
|
|
|
44 |
|
|
void mheap_free(maxHeap* hp) |
45 |
|
|
{ |
46 |
|
|
resize_heap(hp,0); |
47 |
|
|
free(hp); |
48 |
|
|
} |
49 |
|
|
|
50 |
|
|
maxHeap* mheap_create() |
51 |
|
|
{ |
52 |
|
|
maxHeap* res = (maxHeap*) calloc(1,sizeof(maxHeap)); |
53 |
|
|
if (!res) { |
54 |
|
|
fprintf(stderr,"Error allocating heap struct\n"); |
55 |
|
|
return NULL; |
56 |
|
|
} |
57 |
|
|
if (!mheap_init(res)) |
58 |
|
|
return NULL; |
59 |
|
|
return res; |
60 |
|
|
} |
61 |
|
|
|
62 |
|
|
|
63 |
|
|
static void swap_elem(heapElem* e1,heapElem* e2) |
64 |
|
|
{ |
65 |
|
|
heapElem e; |
66 |
|
|
|
67 |
|
|
e = *e1; |
68 |
|
|
*e1 = *e2; |
69 |
|
|
*e2 = e; |
70 |
|
|
} |
71 |
|
|
|
72 |
|
|
static void heapify(maxHeap* hp,int i) |
73 |
|
|
{ |
74 |
|
|
int l,r,m; |
75 |
|
|
|
76 |
|
|
l = mh_left(i); |
77 |
|
|
r = mh_right(i); |
78 |
|
|
if ((l < hp->size) && (hp->heap[l].key > hp->heap[i].key)) |
79 |
|
|
m = l; |
80 |
|
|
else |
81 |
|
|
m = i; |
82 |
|
|
if ((r < hp->size) && (hp->heap[m].key < hp->heap[r].key)) |
83 |
|
|
m = r; |
84 |
|
|
if (m != i) { |
85 |
|
|
swap_elem(&(hp->heap[m]),&(hp->heap[i])); |
86 |
|
|
heapify(hp,m); |
87 |
|
|
} |
88 |
|
|
} |
89 |
|
|
|
90 |
|
|
void mheap_build(maxHeap* hp) |
91 |
|
|
{ |
92 |
|
|
int i; |
93 |
|
|
|
94 |
|
|
for(i=((int) hp->size/2)-1;i>=0;i--) |
95 |
|
|
heapify(hp,i); |
96 |
|
|
hp->state = HP_BUILD; |
97 |
|
|
} |
98 |
|
|
|
99 |
|
|
void mheap_sort(maxHeap* hp) |
100 |
|
|
{ |
101 |
|
|
int i,sz; |
102 |
|
|
|
103 |
|
|
if (hp->state == HP_SORTED) |
104 |
|
|
return; |
105 |
|
|
if (hp->state != HP_BUILD) |
106 |
|
|
mheap_build(hp); |
107 |
|
|
sz = hp->size; |
108 |
|
|
for(i=(hp->size-1);i>0;i--) { |
109 |
|
|
swap_elem(&(hp->heap[0]),&(hp->heap[i])); |
110 |
|
|
hp->size--; |
111 |
|
|
heapify(hp,0); |
112 |
|
|
} |
113 |
|
|
hp->size = sz; |
114 |
|
|
hp->state = HP_SORTED; |
115 |
|
|
} |
116 |
|
|
|
117 |
|
|
|
118 |
|
|
heapElem mheap_remove_max(maxHeap* hp) |
119 |
|
|
{ |
120 |
|
|
heapElem res; |
121 |
|
|
if (hp->size < 1) { |
122 |
|
|
res.key = -HUGE; |
123 |
|
|
res.entity = NULL; |
124 |
|
|
return res; |
125 |
|
|
} |
126 |
|
|
res = hp->heap[0]; |
127 |
|
|
hp->heap[0] = hp->heap[hp->size - 1]; |
128 |
|
|
hp->size--; |
129 |
|
|
heapify(hp,0); |
130 |
|
|
return res; |
131 |
|
|
} |
132 |
|
|
|
133 |
|
|
static int inc_key(maxHeap* hp,int i,g3Float k) |
134 |
|
|
{ |
135 |
|
|
if (k < hp->heap[i].key) { |
136 |
|
|
fprintf(stderr,"New key error in inc_key(mheap)\n"); |
137 |
|
|
hp->state = HP_INVALID; |
138 |
|
|
return 0; |
139 |
|
|
} |
140 |
|
|
hp->heap[i].key = k; |
141 |
|
|
while((i > 0) && (hp->heap[mh_parent(i)].key < hp->heap[i].key)) { |
142 |
|
|
swap_elem(&(hp->heap[mh_parent(i)]),&(hp->heap[i])); |
143 |
|
|
i = mh_parent(i); |
144 |
|
|
} |
145 |
|
|
return 1; |
146 |
|
|
} |
147 |
|
|
|
148 |
|
|
int mheap_insert(maxHeap* hp,g3Float key,void* entity) |
149 |
|
|
{ |
150 |
|
|
if (hp->size == hp->cap) { |
151 |
|
|
if (!resize_heap(hp,hp->cap*2)) { |
152 |
|
|
hp->state = HP_INVALID; |
153 |
|
|
return 0; |
154 |
|
|
} |
155 |
|
|
} |
156 |
|
|
hp->heap[hp->size].entity = entity; |
157 |
|
|
hp->heap[hp->size].key = -HUGE; |
158 |
|
|
hp->size++; |
159 |
|
|
return inc_key(hp,(hp->size - 1),key); |
160 |
|
|
} |
161 |
|
|
|
162 |
|
|
|
163 |
|
|
#ifdef TEST_MHEAP |
164 |
|
|
#include "timeutil.h" |
165 |
|
|
|
166 |
|
|
int main(int argc,char** argv) |
167 |
|
|
{ |
168 |
|
|
g3Float* k; |
169 |
|
|
int i,n; |
170 |
|
|
maxHeap* hp; |
171 |
|
|
heapElem e; |
172 |
|
|
double t; |
173 |
|
|
hp = mheap_create(); |
174 |
|
|
|
175 |
|
|
if (argc > 1) |
176 |
|
|
n = atoi(argv[1]); |
177 |
|
|
else |
178 |
|
|
n = 10; |
179 |
|
|
|
180 |
|
|
t = get_time(); |
181 |
|
|
for(i=0;i<n;i++) { |
182 |
|
|
k = (g3Float*) malloc(sizeof(g3Float)); |
183 |
|
|
*k = 10.0*rand()/RAND_MAX; |
184 |
|
|
if (!mheap_insert(hp,*k,k)) { |
185 |
|
|
fprintf(stderr,"Error inserting\n"); |
186 |
|
|
return EXIT_FAILURE; |
187 |
|
|
} |
188 |
|
|
} |
189 |
|
|
t = get_time() - t; |
190 |
|
|
fprintf(stderr,"insert: %d %f\n",n,t); |
191 |
|
|
t = get_time(); |
192 |
|
|
mheap_sort(hp); |
193 |
|
|
t = get_time() - t; |
194 |
|
|
fprintf(stderr,"sort: %d %f\n",n,t); |
195 |
|
|
for(i=0;i<n;i++) |
196 |
|
|
printf("%d %f \n",i,hp->heap[i].key); |
197 |
|
|
printf("-------------\n"); |
198 |
|
|
t = get_time(); |
199 |
|
|
mheap_build(hp); |
200 |
|
|
t = get_time() - t; |
201 |
|
|
fprintf(stderr,"build: %d %f\n",n,t); |
202 |
|
|
for(i=0;i<n;i++) { |
203 |
|
|
e = mheap_remove_max(hp); |
204 |
|
|
printf("%d %f \n",hp->size,e.key); |
205 |
|
|
if ((i < (n-1)) && (e.key < mheap_get_max(hp).key)) { |
206 |
|
|
fprintf(stderr,"oooops: not sorted\n"); |
207 |
|
|
} |
208 |
|
|
} |
209 |
|
|
return EXIT_SUCCESS; |
210 |
|
|
} |
211 |
|
|
|
212 |
|
|
#endif |