| 1 |
#ifndef lint |
| 2 |
static const char RCSid[] = "$Id$"; |
| 3 |
#endif |
| 4 |
#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 |
