From 1aa5b092dce1eabfc4ac2460abf9454341bc79f1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 18 Jun 2003 13:07:10 +0000 Subject: [PATCH] Added a very simple generic implementation of binomial heaps. Their main virtue is that they are fully dynamic, needing no upper bounds on the number of items nor frequent reallocations. Their main disadvantage is the need of 13 bytes per node. I did implement only those heap operations I'll use in the gatherer, I'll add more later. --- lib/Makefile | 1 + lib/binheap-node.h | 22 ++++++ lib/binheap-test.c | 86 +++++++++++++++++++++++ lib/binheap.h | 166 +++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 275 insertions(+) create mode 100644 lib/binheap-node.h create mode 100644 lib/binheap-test.c create mode 100644 lib/binheap.h diff --git a/lib/Makefile b/lib/Makefile index 17653f51..302b2ddd 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -27,6 +27,7 @@ obj/lib/hash-test: obj/lib/hash-test.o $(LIBSH) obj/lib/str-test: obj/lib/str-test.o $(LIBSH) obj/lib/asort-test: obj/lib/asort-test.o $(LIBSH) obj/lib/redblack-test: obj/lib/redblack-test.o $(LIBSH) +obj/lib/binheap-test: obj/lib/binheap-test.o $(LIBSH) include lib/perl/Makefile include lib/shell/Makefile diff --git a/lib/binheap-node.h b/lib/binheap-node.h new file mode 100644 index 00000000..da03a800 --- /dev/null +++ b/lib/binheap-node.h @@ -0,0 +1,22 @@ +/* + * Sherlock Library -- Binomial Heaps: Declarations + * + * (c) 2003 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#define BH_NODE struct BH_PREFIX(node) +#define BH_HEAP struct BH_PREFIX(heap) + +BH_NODE { + BH_NODE *first_son; + BH_NODE *last_son; + BH_NODE *next_sibling; + byte order; +}; + +BH_HEAP { + BH_NODE root; +}; diff --git a/lib/binheap-test.c b/lib/binheap-test.c new file mode 100644 index 00000000..703fac87 --- /dev/null +++ b/lib/binheap-test.c @@ -0,0 +1,86 @@ +/* + * Sherlock Library -- Binomial Heaps: Testing + * + * (c) 2003 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#include "lib/lib.h" + +#include +#include + +#define BH_PREFIX(x) bht_##x +#define BH_WANT_INSERT +#define BH_WANT_FINDMIN +#define BH_WANT_DELETEMIN +#include "lib/binheap-node.h" + +struct item { + struct bht_node n; + uns key; +}; + +static inline uns bht_key(struct bht_node *n) +{ + return ((struct item *)n)->key; +} + +static inline uns bht_less(struct bht_node *a, struct bht_node *b) +{ + return bht_key(a) < bht_key(b); +} + +static void +bht_do_dump(struct bht_node *a, struct bht_node *expected_last, uns offset) +{ + if (!a) + return; + printf("%*s", offset, ""); + printf("[%d](%d)%s\n", a->order, bht_key(a), a == expected_last ? " L" : ""); + for (struct bht_node *b=a->first_son; b; b=b->next_sibling) + bht_do_dump(b, a->last_son, offset+1); +} + +static void +bht_dump(struct bht_heap *h) +{ + printf("root\n"); + for (struct bht_node *b=h->root.first_son; b; b=b->next_sibling) + bht_do_dump(b, b->last_son, 1); +} + +#include "lib/binheap.h" + +int main(void) +{ + uns i; + struct bht_heap h; +#define N 1048576 +#define K(i) ((259309*i+1009)%N) + + bht_init(&h); + + for (i=0; ikey = K(i); + // printf("Insert %d\n", a->key); + bht_insert(&h, &a->n); + // bht_dump(&h); + } + bht_dump(&h); + ASSERT(bht_key(bht_findmin(&h)) == 0); + for (i=0; ikey); + ASSERT(a->key == i); + // bht_dump(&h); + } + bht_dump(&h); + + return 0; +} diff --git a/lib/binheap.h b/lib/binheap.h new file mode 100644 index 00000000..d8578921 --- /dev/null +++ b/lib/binheap.h @@ -0,0 +1,166 @@ +/* + * Sherlock Library -- Binomial Heaps + * + * (c) 2003 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +/* + * This is a generic implementation of Binomial Heaps. Each time you include + * this file with parameters set in the corresponding preprocessor macros + * as described below, it generates functions for manipulating the particular + * version of the binomial heap. + * + * You need to specify: + * + * BH_PREFIX(x) macro to add a name prefix (used on all global names + * defined by the hash table generator). All further + * names mentioned here except for macro names will be + * implicitly prefixed. + * + * Then you continue by including "lib/binheap-node.h" which defines struct node + * (also prefixed) and struct root. The heap elements are always allocated by + * you and they must include struct node which serves as a handle used for all + * the heap functions and it contains all information needed for heap-keeping. + * The heap itself is also allocated by you and it's represented by struct root. + * + * When you have the declaration of heap nodes, you continue with defining: + * + * less(p,q) returns 1 if the key corresponding to bh_node *p + * is less than the one corresponding to *q. + * + * Then specify what operations you request: + * + * init(heap) -- initialize the heap. + * BH_WANT_INSERT insert(heap, node*) -- insert the node to the heap. + * BH_WANT_FINDMIN node *findmin(heap) -- find node with minimum key. + * BH_WANT_DELETEMIN node *deletemin(heap) -- findmin and delete the node. + * + * Then include "lib/binheap.h| and voila, you have a binomial heap + * suiting all your needs (at least those which you've revealed :) ). + * + * After including this file, all parameter macros are automatically + * undef'd. + */ + +static void +BH_PREFIX(merge)(BH_NODE *a, BH_NODE *b) +{ + BH_NODE **pp = &a->first_son; + BH_NODE *q = b->first_son; + BH_NODE *p, *r, *s; + + while ((p = *pp) && q) + { + /* p,q are the next nodes of a,b; pp points to where p is linked */ + if (p->order < q->order) /* p is smaller => skip it */ + pp = &p->next_sibling; + else if (p->order > q->order) /* q is smaller => insert it before p */ + { + r = q; + q = q->next_sibling; + r->next_sibling = p; + *pp = r; + pp = &r->next_sibling; + } + else /* p and q are of the same order => need to merge them */ + { + if (BH_PREFIX(less)(p, q)) /* we'll hang r below s */ + { + r = q; + s = p; + } + else + { + r = p; + s = q; + } + *pp = p->next_sibling; /* unlink p,q from their lists */ + q = q->next_sibling; + + if (s->last_son) /* merge r to s, increasing order */ + s->last_son->next_sibling = r; + else + s->first_son = r; + s->last_son = r; + s->order++; + r->next_sibling = NULL; + + if (!q || q->order > s->order) /* put the result into the b's list if possible */ + { + s->next_sibling = q; + q = s; + } + else /* otherwise put the result to the a's list */ + { + p = s->next_sibling = *pp; + *pp = s; + if (p && p->order == s->order) /* 3-collision */ + pp = &s->next_sibling; + } + } + } + if (!p) + *pp = q; +} + +#ifdef BH_WANT_INSERT +static void +BH_PREFIX(insert)(BH_HEAP *heap, BH_NODE *a) +{ + BH_NODE sh; + + sh.first_son = a; + a->first_son = a->last_son = a->next_sibling = NULL; + BH_PREFIX(merge)(&heap->root, &sh); +} +#endif + +#ifdef BH_WANT_FINDMIN +static BH_NODE * +BH_PREFIX(findmin)(BH_HEAP *heap) +{ + BH_NODE *p, *best; + + best = NULL; + for (p=heap->root.first_son; p; p=p->next_sibling) + if (!best || BH_PREFIX(less)(p, best)) + best = p; + return best; +} +#endif + +#ifdef BH_WANT_DELETEMIN +static BH_NODE * +BH_PREFIX(deletemin)(BH_HEAP *heap) +{ + BH_NODE *p, **pp, **bestp; + + bestp = NULL; + for (pp=&heap->root.first_son; p=*pp; pp=&p->next_sibling) + if (!bestp || BH_PREFIX(less)(p, *bestp)) + bestp = pp; + if (!bestp) + return NULL; + + p = *bestp; + *bestp = p->next_sibling; + BH_PREFIX(merge)(&heap->root, p); + return p; +} +#endif + +static inline void +BH_PREFIX(init)(BH_HEAP *heap) +{ + bzero(heap, sizeof(*heap)); +} + +#undef BH_PREFIX +#undef BH_NODE +#undef BH_HEAP +#undef BH_WANT_INSERT +#undef BH_WANT_FINDMIN +#undef BH_WANT_DELETEMIN -- 2.39.2