00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065 #include <stdio.h>
00066 #include <stdlib.h>
00067 #include <string.h>
00068 #include <assert.h>
00069
00070 #include "heap.h"
00071 #include "err.h"
00072 #include "ckd_alloc.h"
00073
00074
00076 typedef struct heap_s {
00077 void *data;
00078 int32 val;
00079
00080 int32 nl, nr;
00081 struct heap_s *l;
00082 struct heap_s *r;
00083 } heapnode_t;
00084
00085
00086 #if 0
00087 static void
00088 heap_dump(heapnode_t * top, int32 level)
00089 {
00090 int32 i;
00091
00092 if (!top)
00093 return;
00094
00095 for (i = 0; i < level; i++)
00096 printf(" ");
00097
00098 heap_dump(top->l, level + 1);
00099 heap_dump(top->r, level + 1);
00100 }
00101 #endif
00102
00103
00104 heap_t
00105 heap_new(void)
00106 {
00107 heapnode_t **h;
00108
00109 h = (heapnode_t **) ckd_calloc(1, sizeof(heapnode_t *));
00110 *h = NULL;
00111
00112 return ((heap_t) h);
00113 }
00114
00115
00116 static heapnode_t *
00117 subheap_insert(heapnode_t * root, void *data, int32 val)
00118 {
00119 heapnode_t *h;
00120 void *tmpdata;
00121 int32 tmpval;
00122
00123 if (!root) {
00124 h = (heapnode_t *) ckd_calloc(1, sizeof(heapnode_t));
00125 h->data = data;
00126 h->val = val;
00127 h->l = h->r = NULL;
00128 h->nl = h->nr = 0;
00129 return h;
00130 }
00131
00132
00133 if (root->val > val) {
00134 tmpdata = root->data;
00135 tmpval = root->val;
00136 root->data = data;
00137 root->val = val;
00138 data = tmpdata;
00139 val = tmpval;
00140 }
00141
00142
00143 if (root->nl > root->nr) {
00144 root->r = subheap_insert(root->r, data, val);
00145 root->nr++;
00146 }
00147 else {
00148 root->l = subheap_insert(root->l, data, val);
00149 root->nl++;
00150 }
00151
00152 return root;
00153 }
00154
00155
00156 int32
00157 heap_insert(heap_t heap, void *data, int32 val)
00158 {
00159 heapnode_t **hp;
00160
00161 hp = (heapnode_t **) heap;
00162
00163 *hp = subheap_insert(*hp, data, val);
00164
00165 return 0;
00166 }
00167
00168
00169 static heapnode_t *
00170 subheap_pop(heapnode_t * root)
00171 {
00172 heapnode_t *l, *r;
00173
00174
00175 l = root->l;
00176 r = root->r;
00177
00178 if (!l) {
00179 if (!r) {
00180 ckd_free((char *) root);
00181 return NULL;
00182 }
00183 else {
00184 root->data = r->data;
00185 root->val = r->val;
00186 root->r = subheap_pop(r);
00187 root->nr--;
00188 }
00189 }
00190 else {
00191 if ((!r) || (l->val < r->val)) {
00192 root->data = l->data;
00193 root->val = l->val;
00194 root->l = subheap_pop(l);
00195 root->nl--;
00196 }
00197 else {
00198 root->data = r->data;
00199 root->val = r->val;
00200 root->r = subheap_pop(r);
00201 root->nr--;
00202 }
00203 }
00204
00205 return root;
00206 }
00207
00208
00209 int32
00210 heap_pop(heap_t heap, void **data, int32 * val)
00211 {
00212 heapnode_t **hp, *h;
00213
00214 hp = (heapnode_t **) heap;
00215 h = *hp;
00216
00217 if (!h)
00218 return 0;
00219
00220 *data = h->data;
00221 *val = h->val;
00222
00223 *hp = subheap_pop(h);
00224
00225 return 1;
00226 }
00227
00228
00229 int32
00230 heap_top(heap_t heap, void **data, int32 * val)
00231 {
00232 heapnode_t **hp, *h;
00233
00234 hp = (heapnode_t **) heap;
00235 h = *hp;
00236
00237 if (!h)
00238 return 0;
00239
00240 *data = h->data;
00241 *val = h->val;
00242
00243 return 1;
00244 }
00245
00246 int32
00247 heap_size(heap_t heap)
00248 {
00249 heapnode_t **hp, *h;
00250
00251 hp = (heapnode_t **) heap;
00252 h = *hp;
00253
00254 if (h == NULL)
00255 return 0;
00256 return h->nl + h->nr + 1;
00257 }
00258
00259 int32
00260 heap_destroy(heap_t heap)
00261 {
00262 void *data;
00263 int32 val;
00264
00265
00266 while (heap_pop(heap, &data, &val) > 0);
00267 ckd_free((char *) heap);
00268
00269 return 0;
00270 }