Facebook

Binomial Heaps

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.

Binomial Heap

 

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

Fig 1 : Binomial Heap of 13

 

Details of Binomial Heap in Fig 2

Fig 2 : Details of Binomial Heap in Fig 2

 

Binomial Heap of 15

Fig 3 : Binomial Heap of 15

 

Details of Binomial heap in Fig 3

Fig 4 : 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).

Fig 5 : Structure to represent node of Binomial Heap

 

Example

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

Fig 6 : Binomial Heap

 

Fig 7 : Structure to represent node 9
Fig 8 : Structure to represent node 31

 

Operations on Binomial Heaps

The various operations that can be performed on Binomial heaps are:

  1. Union
  2. Delete Min
  3. Decrease Key
  4. Delete
  5. Insert

 

 

Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar