2 * Sherlock Library -- Binomial Heaps
4 * (c) 2003 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
11 * This is a generic implementation of Binomial Heaps. Each time you include
12 * this file with parameters set in the corresponding preprocessor macros
13 * as described below, it generates functions for manipulating the particular
14 * version of the binomial heap.
16 * You need to specify:
18 * BH_PREFIX(x) macro to add a name prefix (used on all global names
19 * defined by the hash table generator). All further
20 * names mentioned here except for macro names will be
21 * implicitly prefixed.
23 * Then you continue by including "lib/binheap-node.h" which defines struct node
24 * (also prefixed) and struct root. The heap elements are always allocated by
25 * you and they must include struct node which serves as a handle used for all
26 * the heap functions and it contains all information needed for heap-keeping.
27 * The heap itself is also allocated by you and it's represented by struct root.
29 * When you have the declaration of heap nodes, you continue with defining:
31 * less(p,q) returns 1 if the key corresponding to bh_node *p
32 * is less than the one corresponding to *q.
34 * Then specify what operations you request:
36 * <always defined> init(heap) -- initialize the heap.
37 * BH_WANT_INSERT insert(heap, node*) -- insert the node to the heap.
38 * BH_WANT_FINDMIN node *findmin(heap) -- find node with minimum key.
39 * BH_WANT_DELETEMIN node *deletemin(heap) -- findmin and delete the node.
41 * Then include "lib/binheap.h| and voila, you have a binomial heap
42 * suiting all your needs (at least those which you've revealed :) ).
44 * After including this file, all parameter macros are automatically
49 BH_PREFIX(merge)(BH_NODE *a, BH_NODE *b)
51 BH_NODE **pp = &a->first_son;
52 BH_NODE *q = b->first_son;
55 while ((p = *pp) && q)
57 /* p,q are the next nodes of a,b; pp points to where p is linked */
58 if (p->order < q->order) /* p is smaller => skip it */
59 pp = &p->next_sibling;
60 else if (p->order > q->order) /* q is smaller => insert it before p */
66 pp = &r->next_sibling;
68 else /* p and q are of the same order => need to merge them */
70 if (BH_PREFIX(less)(p, q)) /* we'll hang r below s */
80 *pp = p->next_sibling; /* unlink p,q from their lists */
83 if (s->last_son) /* merge r to s, increasing order */
84 s->last_son->next_sibling = r;
89 r->next_sibling = NULL;
91 if (!q || q->order > s->order) /* put the result into the b's list if possible */
96 else /* otherwise put the result to the a's list */
98 p = s->next_sibling = *pp;
100 if (p && p->order == s->order) /* 3-collision */
101 pp = &s->next_sibling;
109 #ifdef BH_WANT_INSERT
111 BH_PREFIX(insert)(BH_HEAP *heap, BH_NODE *a)
116 a->first_son = a->last_son = a->next_sibling = NULL;
117 BH_PREFIX(merge)(&heap->root, &sh);
121 #ifdef BH_WANT_FINDMIN
123 BH_PREFIX(findmin)(BH_HEAP *heap)
128 for (p=heap->root.first_son; p; p=p->next_sibling)
129 if (!best || BH_PREFIX(less)(p, best))
135 #ifdef BH_WANT_DELETEMIN
137 BH_PREFIX(deletemin)(BH_HEAP *heap)
139 BH_NODE *p, **pp, **bestp;
142 for (pp=&heap->root.first_son; p=*pp; pp=&p->next_sibling)
143 if (!bestp || BH_PREFIX(less)(p, *bestp))
149 *bestp = p->next_sibling;
150 BH_PREFIX(merge)(&heap->root, p);
156 BH_PREFIX(init)(BH_HEAP *heap)
158 bzero(heap, sizeof(*heap));
164 #undef BH_WANT_INSERT
165 #undef BH_WANT_FINDMIN
166 #undef BH_WANT_DELETEMIN