What are priority queues or heaps in C++? We already have various data structures to store our data but what’s so special about heaps? In this article, we will look at the answers to these questions. We will further try to understand the implementation of heaps in C++. So let’s start with the motivation to implement heaps.

## Why Implement Heaps in C++?

Whenever we need to find the minimum or the maximum element among some given number of elements say N, we employ heaps for this purpose. The reason is very simple, heaps do this work in minimum possible time complexity and resources.

The table given below compares the space and time complexities of different data structures for basic operations.

Operation | Vector | Sorted Array | BST | Heap |

Insert/Push | O(1) | O(N) | O(Height) | O(Log_{2}N) |

Pop | O(N) | O(1) | O(Height) | O(Log_{2}N) |

Get | O(1) | O(1) | O(Height) | O(Log_{2}N) |

As you can clearly notice that the heap offers the best time complexity for all the operations. This accounts for the need for heaps.

## What Is A Heap?

A heap is a data structure that stores the minimum or the maximum element at the top of the heap based on its type. A heap can be of two types, it can either be a `min-heap`

or a `max-heap`

. A min-heap gives nearly constant time access to the minimum element among all the elements at any point in time. A max-heap differs in the sense that it gives access to the maximum element among all the elements.

**Note:** A heap is a *complete binary tree*. This is the reason why we can represent heaps as arrays(A complete binary tree can be represented as an array).

`Heap Order Property:`

Every parent > Children: Max-Heap

`Heap Order Property:`

Every child > Parent: Min-Heap

## Representation Of Heaps As Arrays

Though heaps are visualized as non-linear data structures but in practice, we use arrays to implement heaps. A simple visualization of a heap using an array is given below.

Each child node is related to the parent node by the following relation.

`right_child = 2*parent`

`left_child = 2*parent + 1`

**Note:** This relation is valid when the indexing is 1 based.

## Implementing Heaps In C++

Let’s now move on towards the heap implementation in C++. The implementation will be in two steps, in the first step we’ll learn to insert an element in the heap. Later we’ll implement the function for the removal of elements

### Create a Custom Heap Class

```
class Heap
{
vector <int> v; // array to store the data
bool min_heap; // by default we will generate a min_heap
public:
// constructor
Heap(int default_size = 10, bool type = true)
{
v.reserve(default_size);
v.push_back(-1); // to block the 0th index
min_heap = type;
}
//custom comparator function
bool compare(int a, int b)
{
if(min_heap)
return a < b;
return a > b;
}
};
```

### Insertion In Heaps (Min Heap)

**Step 1:** To insert an element in the tree, we insert the element at the end of the array. But later we will change the position of the element to satisfy the heap order property.

**Step 2:** We will compare the data of the node with the `parent node`

. If parent > children, we will swap their values.

**Step 3:** But *step 2* will disturb the ordering of the nodes on top of it. To solve this problem, we will repeat the same process till we hit the root node.

### C++ Code For Insertion in Heaps

```
// function to insert an element in the heap
void push(int data)
{
v.push_back(data);
int index = v.size() - 1; // index of the last pushed element
int parent = index/2;
//while loop to run till every node of the heap is fixed
while(index > 1 && compare(v[index], v[parent]))
{
// if the heap order property is not satisfied, swap the elements
swap(v[index], v[parent]);
index = parent; // change the index of the child
parent /= 2;
}
}
```

### Removing Min/Max Element From Helps in C++

The minimum/maximum element is always present at the top depending upon the type of the heap. When we remove this element, the heap order property is disturbed. Now a new minimum/maximum element is to be shifted to the top. So let’s move on to the implementation of the pop function in a heap.

**Step 1:** You can not break the tree from the root. Swap the first(topmost) element of the array and swap it with the last element. So that we can remove the element from the end of the array.

**Step 2:** Shrink the array from the end. Now the heap order property will get disturbed because of the shifting of the last element to the front. To restore the heap order property once again, we will develop a function `heapify()`

. This function will fix the tree recursively until all the nodes satisfy the heap order property.

### Code For Extraction Of The Topmost Element from Heaps in C++

```
void heapify(int index)
{
int min_index = index;
int left = 2 * index;
int right = left + 1;
int last = v.size() - 1;
// both the children should have the value between
// 1 <= child <= last
if(left <= last && compare(v[left], v[index]))
min_index = left;
if(right <= last && compare(v[right], v[index]))
min_index = right;
if(min_index != index)
{
swap(v[index], v[min_index]);
heapify(min_index);
}
}
void pop()
{
int last = v.size() - 1;
swap(v[1], v[last]);
v.pop_back();
heapify(1);
}
```

## Time Complexity Analysis

**Note:** The height of a complete binary tree is: O(Log_{2}N).

### Insertion

We start by inserting the new element at the end and later we push it upwards until all the nodes are fixed. This operation can take at most *Log _{2}N* iterations since each time the value of the index of the parent becomes half of the previous value.

`Complexity:`

O(Log_{2}N)

### Heapify

The comparison starts from the index of the given node, in the worst case the index passed as the argument can be the first index. This means that the element can move at most *Log _{2}N* steps downwards.

`Complexity:`

O(Log_{2}N)

### Deletion

Each deletion operation swaps the first and the last element in the vector, and later calls the heapify() operation on the root

`Complexity:`

O(Log_{2}N)

## Conclusion

Let’s conclude this article by recalling what we discussed today. At first, we looked at the need for heaps. Heaps are very powerful data structures that offer nearly constant time access to the minimum/maximum element at any point in time. We further learned the representation, insertion of an element, and deletion of an element from a heap. In the end, we proved the time complexity of various operations associated with heaps.

## References

To learn more about heaps, you can visit the following websites.

https://en.cppreference.com/w/cpp/algorithm/make_heap

https://en.wikipedia.org/wiki/Heap_(data_structure)