## 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:

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

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

- create binary tree from array
- Start from the first index of non-leaf node with index
**n/2-1**. - set largest = i
- 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 - Swap
**largest**with current element. - 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`

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

Note :For

`Min Heap`

, parent node is alwayssmallerthan 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`

:

- Select value to be removed.
- Swap it with the last element.
- Remove the last element.
- Heapify the tree.

Note : For

`Min Heap`

, both child nodes aregreaterthan 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); } }