# Complete Guide To Heaps

## Heaps

A heap is a complete binary tree in which every node key is compared with its children and arranged accordingly. It is also called as a binary heap.
It has two properties :

• All levels are full, except the last one, which is filled from left to right
• Every node should have element greater (or smaller) than or equal to all its children nodes. (duplicates are allowed)

The ordering is of two types:

1. Max heap : A max heap is a complete binary tree in which the key value in each node is greater than or equal to the key values in the child node.
1. Min heap : A min heap is a complete binary tree in which the key value in each node is smaller than or equal to the key values in its child node.

>

As heap is a complete binary tree, height of the tree will be `logN`

## Array Representation of Heaps

Heaps can be easily represented as an array since it is a complete binary tree.
Array-based representation is space-efficient.

## Operations on Heap

### Heapify

The process of creating a heap data structure froma binary tree is known as Heapify.
Min-Heap or a Max-Heap are constructed using this process.

1. create binary tree from array
2. Start from the first index of non-leaf node with index n/2-1.
3. set largest = i
4. index of :
[left child] = `2i + 1`
[right child] = `2i + 2`.
If left child is greater than current node (i.e. element at ith index), set index of left child as largest.
If right child is greater than current node , set index of right child as largest
5. Swap largest with current element.
6. Repeat steps 2-6 until the subtrees are also heapified.
```void Heapify(vector<int> &heap, int i)
{
int size = heap.size();
int largest = i;
int l = 2 * i + 1; //left child
int r = 2 * i + 2; //right child
if (l < size && heap[l] > heap[largest])
largest = l;
if (r < size && heap[r] > heap[largest])
largest = r;

if (largest != i)
{
swap(&heap[i], &heap[largest]); // perform swapping
Heapify(heap, largest);
}
}
```

### Insertion in Heap

Inserting in a `Max heap`

1. Create a new node. (If no node present)
2. If a node is already present, just insert the new node at the end (last node from left to right.)
3. Heapify

Note :For `Min Heap`, parent node is always smaller than newNode.

```void insert(vector<int> &heap, int val)
{
int size = heap.size();
if (size == 0)
{
heap.push_back(val);
}
else
{
heap.push_back(val);
for (int i = size/2-1; i >= 0; i--)
{
heapify(heap, i);
}
}
}
```

### Deletion in Heap

To delete a node in `Max heap`:

1. Select value to be removed.
2. Swap it with the last element.
3. Remove the last element.
4. Heapify the tree.

Note : For `Min Heap`, both child nodes are greater than the current node.

```void hDelete(vector<int> &heap, int val)
{
int size = heap.size();
int i;
for (i = 0; i < size; i++)
{
if (val == heap[i])
break;
}
swap(&heap[i], &heap[size - 1]);

heap.pop_back();
for (int i = size/2-1; i >= 0; i--)
{
heapify(heap, i);
}
}
```
[gravityforms id="5" description="false" titla="false" ajax="true"]