Lines Matching refs:heap
34 /* A binary min heap. The usual properties hold: the root is the lowest
38 * The heap function try hard to detect corrupted tree nodes at the cost
41 struct heap {
51 HEAP_EXPORT(void heap_init(struct heap* heap));
52 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
53 HEAP_EXPORT(void heap_insert(struct heap* heap,
56 HEAP_EXPORT(void heap_remove(struct heap* heap,
59 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));
63 HEAP_EXPORT(void heap_init(struct heap* heap)) {
64 heap->min = NULL;
65 heap->nelts = 0;
68 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
69 return heap->min;
73 static void heap_node_swap(struct heap* heap,
100 heap->min = child;
107 HEAP_EXPORT(void heap_insert(struct heap* heap,
121 * heap so we always insert at the left-most free node of the bottom row.
124 for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
127 /* Now traverse the heap using the path we calculated in the previous step. */
128 parent = child = &heap->min;
142 heap->nelts += 1;
144 /* Walk up the tree and check at each node if the heap property holds.
145 * It's a min heap so parent < child must be true.
148 heap_node_swap(heap, newnode->parent, newnode);
151 HEAP_EXPORT(void heap_remove(struct heap* heap,
161 if (heap->nelts == 0)
168 for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
171 /* Now traverse the heap using the path we calculated in the previous step. */
172 max = &heap->min;
192 heap->nelts -= 1;
196 if (child == heap->min) {
197 heap->min = NULL;
216 heap->min = child;
223 /* Walk down the subtree and check at each node if the heap property holds.
224 * It's a min heap so parent < child must be true. If the parent is bigger,
235 heap_node_swap(heap, child, smallest);
243 heap_node_swap(heap, child->parent, child);
246 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
247 heap_remove(heap, heap->min, less_than);