Introduction

Binomial heap is a data structure that supports for example efficient merge of two heaps, insertions, deletions or access to the minimum element. All these operations are logarithimc in the worst case. If the merge is not significat, it is usually better to use simplier binary heaps.

They are defined in ucw/binheap.h as generics generated by preprocessor, some common definitions are also in ucw/binheap-node.h.

Common definitions

struct bh_node {
  struct bh_node *first_son;
  struct bh_node *last_son;
  struct bh_node *next_sibling;
  byte order;
};

Common header of binomial heap nodes.

struct bh_heap {
  struct bh_node root;
};

A binomial heap.

Interface to the generator

To use the binomial heaps, you need to specify:

  • BH_PREFIX(x)  — macro to add a name prefix (used on all global names defined by the generator). All further names mentioned here except for macro names will be implicitly prefixed.

Then you continue by including ucw/binheap-node.h which defines struct bh_node and struct bh_heap (both without prefix). The heap elements are always allocated by you and they must include struct bh_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 bh_heap.

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 (always defined).

  • insert(heap\*, node\*) — insert the node to the heap (BH_WANT_INSERT).

  • node\* findmin(heap\*) — find node with minimum key (BH_WANT_FINDMIN).

  • node\* deletemin(heap\*) — findmin and delete the node (BH_WANT_DELETEMIN).

Then include ucw/binheap.h and voila, you have a binomial heap suiting all your needs (at least those which you’ve revealed :) ).

You also get a iterator macro at no extra charge:

BH_FOR_ALL(bh_prefix, heap*, variable)
  {
    // node* variable gets declared automatically
    do_something_with_node(variable);
    // use BH_BREAK and BH_CONTINUE instead of break and continue
    // you must not alter contents of the binomial heap here
  }
BH_END_FOR;

After including this file, all parameter macros are automatically undef’d.