Binomial Heaps are similar to binary heaps with additional feature of implementing binomial series as sequence of trees.The heap(Fig 1) is represented using left child right sibling pointers.It has three links per node (parent,left,right) and the roots of tree are connected using single linked list.The degrees of tree decrease from left to right.
Properties of Binomial Heap
- Each Binomial tree in the heap obey min-heap property.
- There can be only 0 or 1 binomial trees for each order .
The root value of every binomial tree is smaller than its children and there will be at most log n +1 binomial trees of binomial heap with n nodes.
Each binomial tree corresponds to one digit in binary representation of a number n.For e.g.the binary representation of 13(Fig 2) is 1101(23+22+20=8+4+1).The binomial heap will have 13 nodes with binomial trees of order 3,2 and 0 respectively.The orders came from the powers of 2. Either there will be no tree or there will one tree of each order i.e we cannot have any two trees of same order in the binomial heap.Similarly for a number like 15,the binary representation is 1111(23+22 +21 +20 =8+4+2+1).The binomial heap will have 15 nodes(Fig 4)with binomial trees of order 3,2,1,0 respectively.
Binomial Heap of 13
Details of Binomial Heap in Fig 2
Binomial Heap of 15
Details of Binomial heap in Fig 3
Representing Binomial Heaps
The nodes in the binomial heap can be represented by a structure with parent,key,degree,child and sibling attributes ( Fig 5).
Consider the binomial heap as given in Fig 6.Say we want to represent 9(Say) then the structure would be like as given in Fig 7 or if we want represent 31 the structure would be like as given in Fig 8
Operations on Binomial Heaps
The various operations that can be performed on Binomial heaps are:
- Delete Min
- Decrease Key