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 "ckd_alloc.h"
00072
00073
00075 typedef struct heap_s {
00076 void *data;
00077 int32 val;
00078
00079 int32 nl, nr;
00080 struct heap_s *l;
00081 struct heap_s *r;
00082 } heapnode_t;
00083
00084
00085 #if 0
00086 static void
00087 heap_dump(heapnode_t * top, int32 level)
00088 {
00089 int32 i;
00090
00091 if (!top)
00092 return;
00093
00094 for (i = 0; i < level; i++)
00095 printf(" ");
00096
00097 heap_dump(top->l, level + 1);
00098 heap_dump(top->r, level + 1);
00099 }
00100 #endif
00101
00102
00103 heap_t
00104 heap_new(void)
00105 {
00106 heapnode_t **h;
00107
00108 h = (heapnode_t **) ckd_calloc(1, sizeof(heapnode_t *));
00109 *h = NULL;
00110
00111 return ((heap_t) h);
00112 }
00113
00114
00115 static heapnode_t *
00116 subheap_insert(heapnode_t * root, void *data, int32 val)
00117 {
00118 heapnode_t *h;
00119 void *tmpdata;
00120 int32 tmpval;
00121
00122 if (!root) {
00123 h = (heapnode_t *) ckd_calloc(1, sizeof(heapnode_t));
00124 h->data = data;
00125 h->val = val;
00126 h->l = h->r = NULL;
00127 h->nl = h->nr = 0;
00128 return h;
00129 }
00130
00131
00132 if (root->val > val) {
00133 tmpdata = root->data;
00134 tmpval = root->val;
00135 root->data = data;
00136 root->val = val;
00137 data = tmpdata;
00138 val = tmpval;
00139 }
00140
00141
00142 if (root->nl > root->nr) {
00143 root->r = subheap_insert(root->r, data, val);
00144 root->nr++;
00145 }
00146 else {
00147 root->l = subheap_insert(root->l, data, val);
00148 root->nl++;
00149 }
00150
00151 return root;
00152 }
00153
00154
00155 int32
00156 heap_insert(heap_t heap, void *data, int32 val)
00157 {
00158 heapnode_t **hp;
00159
00160 hp = (heapnode_t **) heap;
00161
00162 *hp = subheap_insert(*hp, data, val);
00163
00164 return 0;
00165 }
00166
00167
00168 static heapnode_t *
00169 subheap_pop(heapnode_t * root)
00170 {
00171 heapnode_t *l, *r;
00172
00173
00174 l = root->l;
00175 r = root->r;
00176
00177 if (!l) {
00178 if (!r) {
00179 ckd_free((char *) root);
00180 return NULL;
00181 }
00182 else {
00183 root->data = r->data;
00184 root->val = r->val;
00185 root->r = subheap_pop(r);
00186 root->nr--;
00187 }
00188 }
00189 else {
00190 if ((!r) || (l->val < r->val)) {
00191 root->data = l->data;
00192 root->val = l->val;
00193 root->l = subheap_pop(l);
00194 root->nl--;
00195 }
00196 else {
00197 root->data = r->data;
00198 root->val = r->val;
00199 root->r = subheap_pop(r);
00200 root->nr--;
00201 }
00202 }
00203
00204 return root;
00205 }
00206
00207
00208 int32
00209 heap_pop(heap_t heap, void **data, int32 * val)
00210 {
00211 heapnode_t **hp, *h;
00212
00213 hp = (heapnode_t **) heap;
00214 h = *hp;
00215
00216 if (!h)
00217 return 0;
00218
00219 *data = h->data;
00220 *val = h->val;
00221
00222 *hp = subheap_pop(h);
00223
00224 return 1;
00225 }
00226
00227
00228 int32
00229 heap_top(heap_t heap, void **data, int32 * val)
00230 {
00231 heapnode_t **hp, *h;
00232
00233 hp = (heapnode_t **) heap;
00234 h = *hp;
00235
00236 if (!h)
00237 return 0;
00238
00239 *data = h->data;
00240 *val = h->val;
00241
00242 return 1;
00243 }
00244
00245
00246 int32
00247 heap_destroy(heap_t heap)
00248 {
00249 void *data;
00250 int32 val;
00251
00252
00253 while (heap_pop(heap, &data, &val) > 0);
00254 ckd_free((char *) heap);
00255
00256 return 0;
00257 }