# Implementation and Merging of Heaps

### Implementation

Heaps of **n** **keys** can be represented by array of **length n+1**(Fig 2).For a node at **rank i** ,the **left child** is at **rank 2i +1** and the **right child** is at rank **2i +2**.The links between nodes are not stored explicitly.

- In Fig 1,heap has
**7**keys i.e**n =7.** - Array will be of
**length 8**(n+1=7+1).

### Merging two heaps

If two heaps are to be **merged** and a **key(k)** has to be inserted then we follow these steps :

- A
**new heap**is created with**root node**storing**k**and two given heaps as**subtrees**. - Perform
**downheap**to restore**relational**property of heap.

**Example**

Given are the two heaps h1 and h2 in Fig 3.We need to merge them and add 5 to it.

A new heap** h3 ** is created with root node storing **5** and** h1,h2 as subtrees**(Fig 4).

Perform downheap operation to restore **heap property**(Fig 5).

## Comments

So empty here ... leave a comment!