Data Structures and Algorithms

Binomial Heaps

Printable Version

A binomial heap class is easy to implement if you have a robust linked list class to work with since most of the heap's methods simply call the methods of the underlying linked list class. The root list of a binomial heap is implemented as a circular doubly-linked list. The children of a node in a binomial heap are kept as a circular doubly-linked list as well.

We will assume that the ordering of the heap (min-heap or max-heap) is specified via a comparator function that is passed into the constructor of the heap. The constructor caches this comparator and initializes its root list, a pointer to the most extreme node in the root list, and the heap's size:

function newBinheap(comparator) { set b to the allocation of a binheap set b's comparator to the given comparator set b's root list to a new linked list (via linked-list constructor) set b's extreme pointer to null set b's size to zero return b }The

function union(b,donor) { //b and donor are binomial heaps merge the root list of the donor into the root list of b (via linked-list union) increment b's size by donor's size set donor's root list to a new empty linked list set donor's size to zero set donor's extreme pointer to null consolidate the root list of b using b's comparator }The

function insert(b,v) { //b is a binomial heap, v is the value to be inserted set a variable n to a new node containing value v set the parent of n to n set the children pointer of n to a new (empty) linked list insert n into the rootlist of b (via linked-list insert) increment b's size consolidate the root list of b using b's comparator return n }The

function decreaseKey(b,n,v) { set n's value to the new value v bubble up the new value using b's comparator and return the node where the new value finishes up (also update b's extreme value pointer, if necessary) }The

function bubbleUp(b,n) { if n is the root of a subheap return n; else if b's comparator says the n's value isn't smaller than its parent's return n; else { inform the value of n that n's parent is the new owner inform the value of n's parent that n is the new owner swap the values of n and and n's parent return bubbleUp(b,n's parent); } }The

function delete(b,n) { decreaseKey(b,n,null) extractMin(b); }Note: the comparator function has to be implemented so that it treats a null value as more extreme than any other value.

The

function extractMin(b) { set a variable y to the extreme node in b remove y from b's root list (via linked-list remove) // the children of y are a linked list set each of the children's parent to point to themselves merge the children of y into b's root list (via linked-list union) consolidate b's root list using b's comparator decrement b's size return y's value }Consolidation is the most complicated task in maintaining a binomial heap because there is no analogous linked-list method. The basic idea is to move all the subheaps from the root root to a consolidation array and then moving them back into the root list:

function consolidate(b) { //create the consolidation array D calculate D's size: (log (base 2) of b's size) + 1 set a variable D to the allocation of an array of D's size initialize the D array to nulls //place all the subheaps in the D array, combining as necessary */ while b's root list is not empty { set a variable spot to the head node in b's root list remove spot from the root list (via linked-list remove) update the D array with spot } //transfer the D array back to the heap, keeping track of the extreme value set b's extreme pointer to null for (i = 0; i < D's size; ++i) { if D[i] not equal to null { insert D[i] into b's root list (via the linked-list's insert method) update b's extreme pointer if it's null or b's comparator indicates that D[i] is more extreme } } free the D array (if needed) }Updating the consolidation array involves putting the subheap into an empty slot in the array, as indicated by the degree of the subheap. If the slot indicated by the degree is not empty, the original subheap and the subheap in the consolidation array are merged. This merged subheap is then placed into the consolidation array at the next higher slot. Of course, if this new slot is not empty, the merging process continues:

function updateConsolidationArray(D,spot) { set a variable degree to the number of spot's children (using linked-list size) while (D[degree] != null) { combine spot and D[degree], setting spot to the combined subheap set D[degree] to null, since that slot is now empty increment degree } set D[degree] to spot }The

function combine(b,x,y) { if b's comparator says x's value is more extreme than y's { insert y into the children of x (via linked list insert) set the parent of y to x return x } else { insert x into the children of y (via linked list insert) set the parent of x to y return y } }Although some function names reflect a min-heap (

The remaining functions of a binomial implementation are left to the reader.