Lines Matching refs:heap
33 /* A binary min heap. The usual properties hold: the root is the lowest
37 * The heap function try hard to detect corrupted tree nodes at the cost
40 struct heap {
50 HEAP_EXPORT(void heap_init(struct heap* heap));
51 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
52 HEAP_EXPORT(void heap_insert(struct heap* heap,
55 HEAP_EXPORT(void heap_remove(struct heap* heap,
58 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));
62 HEAP_EXPORT(void heap_init(struct heap* heap)) {
63 heap->min = NULL;
64 heap->nelts = 0;
67 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
68 return heap->min;
72 static void heap_node_swap(struct heap* heap,
99 heap->min = child;
106 HEAP_EXPORT(void heap_insert(struct heap* heap,
120 * heap so we always insert at the left-most free node of the bottom row.
123 for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
126 /* Now traverse the heap using the path we calculated in the previous step. */
127 parent = child = &heap->min;
141 heap->nelts += 1;
143 /* Walk up the tree and check at each node if the heap property holds.
144 * It's a min heap so parent < child must be true.
147 heap_node_swap(heap, newnode->parent, newnode);
150 HEAP_EXPORT(void heap_remove(struct heap* heap,
160 if (heap->nelts == 0)
167 for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
170 /* Now traverse the heap using the path we calculated in the previous step. */
171 max = &heap->min;
181 heap->nelts -= 1;
189 if (child == heap->min) {
190 heap->min = NULL;
209 heap->min = child;
216 /* Walk down the subtree and check at each node if the heap property holds.
217 * It's a min heap so parent < child must be true. If the parent is bigger,
228 heap_node_swap(heap, child, smallest);
236 heap_node_swap(heap, child->parent, child);
239 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
240 heap_remove(heap, heap->min, less_than);