Binomial Heaps

http://install4install.com

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

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.

Screen Shot 2014-06-02 at 2.35.41 PM

Fig 1 : 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

Screen Shot 2014-06-02 at 3.11.42 PM

Fig 2 : Binomial Heap of 13

 

Details of Binomial Heap in Fig 2

Screen Shot 2014-06-02 at 3.14.04 PM

Fig 3 : Details of Binomial Heap in Fig 2

 

Binomial Heap of 15

Screen Shot 2014-06-04 at 2.42.02 PM

Fig 3 : Binomial Heap of 15

 

Details of Binomial heap in Fig 3

Screen Shot 2014-06-04 at 2.44.42 PM

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).

Screen Shot 2014-06-05 at 3.41.10 PM

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

Screen Shot 2014-06-05 at 3.40.58 PM

Fig 6 : Binomial Heap

 

Screen Shot 2014-06-05 at 3.44.45 PM

Fig 7 : Structure to represent node 9

Screen Shot 2014-06-05 at 3.46.12 PM

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

 

 



Short URL: http://tinyit.cc/de9cf4
Author: Cusp2207 on June 4, 2014
Category: Computer Science, Data Structures
Tags:

Leave a Reply

Last articles