A Heap is a** Binary tree**(Refer http://letslearncs.com/binary-trees/) that stores** keys** at it’s** internal nodes** and satisfies two additional properties which are :

- Relational Property
- Structural Property

### Relational Property

It follows either **Min-Heap** or **Max-Heap **property.The **Max-Heap **property says that **keys** of each and every **child ** will be **less** than the** key ** of **parent**(Fig 2)whereas** ****Min-Heap ** property says that ** keys** of each and every child are either **greater** than or **equal** to the** key** of **parent**(Fig 1).

### Structural Property

All the levels are **full** except the **last level** which is** left justified**.Left justified means that the parents of terminal nodes will have left child and may/may not have right child(Fig 4).Tree in Fig 3 fails to satisfy structural property.

### Height of a Heap

The height of heap is **O(log n).**

- Let h be the
**height**of**heap**with**n keys**. - The maximum no. of keys in heap can be
**2**^{n.} - Since there 2
^{i }at depth i =0,1,2,3,….h-1 and at least one key at depth h,we have**1 +2 +4 + 2**^{h-1 }**+1**. - Thus n=
**2**and^{h }**height= O( log n).** **h=O(log n).**

### Insertion in Heap

The insertion in **Heap** follows three steps :

- Find the
**node**(Say n) where**key**(k) has to be inserted. - Store
**key(k)**at**node(n)**. - After the insertion of new key,heap property can get violated.
- Use
**Upheap**technique to restore heap property. - The upheap technique swaps the key along with the
**upward**path from the insertion node. - This method is followed until the key(k) reaches a node whose parent has a smaller/equal value to k.

**Example**

### Removal from a Heap

- This method removes the
**root**i.e the minimum value from the heap. - The
**root**is deleted and the**last key**takes the place at root node - Downheap technique is followed till the heap property is restored.
- Downheap swaps key along the
**downward**path. - Terminate downheap method leaf/terminal level is reached and key of parent is less than key of child.

**Example**