# 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.**

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**(2^{3}+2^{2}+2^{0}=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**(2^{3}+2^{2 }+2^{1 }+2^{0} =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).

**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

### Operations on Binomial Heaps

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

- Union
- Delete Min
- Decrease Key
- Delete
- Insert

## Comments

So empty here ... leave a comment!