fheap.c (4715B)
1 #include "fheap.h" 2 3 void fnode_init(fnode_t *node, const uint64_t value, void *data) { 4 node->children = NULL; 5 node->parent = NULL; 6 node->left = node; 7 node->right = node; 8 node->nchildren = 0; 9 node->marked = 0; 10 11 node->value = value; 12 node->data = data; 13 } 14 15 void fnode_clear(fnode_t *node) { 16 // clear children recursively 17 fnode_t *c, *d; 18 size_t n = node->nchildren; 19 c = node->children; 20 size_t i; 21 for (i = 0; i < n; i++) { 22 d = c->right; 23 fnode_clear(c); 24 c = d; 25 } 26 27 free(node); 28 } 29 30 void fheap_init(fheap_t *heap) { 31 heap->min = NULL; 32 heap->head = NULL; 33 heap->n = 0; 34 } 35 36 void fheap_clear(fheap_t *heap) { 37 fnode_t *c = heap->head; 38 fnode_t *d = c->right; 39 40 while (d != c) { 41 fnode_t *t = d->right; 42 fnode_clear(d); 43 d = t; 44 } 45 fnode_clear(c); 46 47 heap->min = NULL; 48 heap->head = NULL; 49 heap->n = 0; 50 } 51 52 static inline void insert_leftof(fnode_t *x, fnode_t *y) { 53 fnode_t *x_left = x->left; 54 x->left = y; 55 y->parent = x->parent; 56 y->right = x; 57 y->left = x_left; 58 x_left->right = y; 59 } 60 61 fnode_t *fheap_insert(fheap_t *heap, const uint64_t value, void *data) { 62 fnode_t *nnode = malloc(sizeof(*nnode)); 63 64 fnode_init(nnode, value, data); 65 66 if (heap->min == NULL) { 67 heap->head = nnode; 68 heap->min = nnode; 69 } else { 70 insert_leftof(heap->head, nnode); 71 if (nnode->value < (heap->min)->value) { 72 heap->min = nnode; 73 } 74 } 75 76 heap->n++; 77 78 return nnode; 79 } 80 81 static inline void remove_node(fnode_t *x) { 82 (x->left)->right = x->right; 83 (x->right)->left = x->left; 84 } 85 86 static inline void fheap_link(fheap_t *heap, fnode_t *y, fnode_t *x) { 87 remove_node(y); 88 if (heap->head == y) 89 heap->head = y->right; 90 if (x->children != NULL) { 91 insert_leftof(x->children, y); 92 } else { 93 x->children = y; 94 y->parent = x; 95 y->left = y; 96 y->right = y; 97 x->nchildren = 0; 98 } 99 x->nchildren++; 100 y->marked = 0; 101 } 102 103 static inline void consolidate(fheap_t *heap) { 104 size_t i, deg; 105 fnode_t *a[heap->n]; 106 107 for (i = 0; i < heap->n; i++) 108 a[i] = NULL; 109 110 fnode_t *c = heap->head; 111 fnode_t *head_list[heap->n]; 112 size_t nheads = 0; 113 do { 114 head_list[nheads] = c; 115 nheads++; 116 c = c->right; 117 } while (c != heap->head); 118 119 size_t max_deg = 0; 120 121 fnode_t *x, *y; 122 for (i = 0; i < nheads; i++) { 123 c = head_list[i]; 124 125 deg = c->nchildren; 126 x = c; 127 while (a[deg] != NULL) { 128 if (x->value > a[deg]->value) { 129 y = x; 130 x = a[deg]; 131 } else { 132 y = a[deg]; 133 } 134 135 fheap_link(heap, y, x); 136 137 a[deg] = NULL; 138 deg++; 139 } 140 141 a[deg] = x; 142 143 if (deg > max_deg) 144 max_deg = deg; 145 } 146 147 heap->head = NULL; 148 heap->min = NULL; 149 for (i = 0; i < max_deg + 1; i++) { 150 if (a[i] != NULL) { 151 if (heap->head == NULL) { 152 heap->head = a[i]; 153 heap->min = a[i]; 154 a[i]->left = a[i]; 155 a[i]->right = a[i]; 156 } else { 157 insert_leftof(heap->head, a[i]); 158 if (a[i]->value < (heap->min)->value) 159 heap->min = a[i]; 160 } 161 } 162 } 163 } 164 165 fnode_t *fheap_extract_min_node(fheap_t *heap) { 166 fnode_t *z = heap->min; 167 fnode_t *c, *d; 168 if (z != NULL) { 169 if (z->nchildren > 0) { 170 c = z->children; 171 do { 172 d = c->right; 173 c->parent = NULL; 174 insert_leftof(heap->head, c); 175 c = d; 176 } while (c != z->children); 177 z->children = NULL; 178 } 179 180 remove_node(z); 181 182 if (z == z->right) { 183 heap->min = NULL; 184 heap->head = NULL; 185 } else { 186 heap->min = z->right; 187 if (heap->head == z) 188 heap->head = z->right; 189 consolidate(heap); 190 } 191 192 heap->n--; 193 } 194 195 return z; 196 } 197 198 uint64_t fheap_extract_min(void **data, fheap_t *heap) { 199 fnode_t *z = fheap_extract_min_node(heap); 200 201 uint64_t value = z->value; 202 *data = z->data; 203 204 z->nchildren = 0; 205 z->children = NULL; 206 fnode_clear(z); 207 208 return value; 209 } 210 211 static inline void fheap_cut(fheap_t *heap, fnode_t *x, fnode_t *y) { 212 remove_node(x); 213 if (y->children == x) { 214 if (x->right == x) { 215 y->children = NULL; 216 } else { 217 y->children = x->right; 218 } 219 } 220 y->nchildren--; 221 222 insert_leftof(heap->head, x); 223 x->parent = NULL; 224 x->marked = 0; 225 } 226 227 static void fheap_cascading_cut(fheap_t *heap, fnode_t *y) { 228 fnode_t *z = y->parent; 229 if (z != NULL) { 230 if (y->marked == 0) { 231 y->marked = 1; 232 } else { 233 fheap_cut(heap, y, z); 234 fheap_cascading_cut(heap, z); 235 } 236 } 237 } 238 239 void fheap_decrease_value(fheap_t *heap, fnode_t *node, const uint64_t value) { 240 node->value = value; 241 fnode_t *y = node->parent; 242 if (y != NULL && node->value < y->value) { 243 fheap_cut(heap, node, y); 244 fheap_cascading_cut(heap, y); 245 } 246 247 if (node->value < (heap->min)->value) 248 heap->min = node; 249 }