Table of Contents

## Introduction

We all have come across a term called Heap. Generally, we have used Heap as a memory storage area where the storage occurs in dynamic memory allocation, right? Well,

Heap is basically a tree type data structure which is used in various process scheduling operations which means it is used in memory use also.

It is a very interesting data structure as it uses some properties of the tree and reduces the time complexity of some significantly complex programmes. To define it, Heap is basically a tree data structure where each node is arranged in a specific order (in order of their priorities). Generally, we use Binary heaps i.e., Heaps nodes will contain at most two children. We will be discussing only Binary Heaps here.

**Also read about the Importance of learning Data Structures for C++**

**Binary Heap**

As discussed above binary heaps have nodes in a particular order and hence, we can categorise it into two types:

**MinHeap****MaxHeap**

Heap data structure can also be referred as **priority queue** where the name suggests the elements are queued in order of a particular priority. Initially we will see the implementation of this manually then we will use C++ STL for further discussion.

In MinHeap, the parent node value must be smaller than the child nodes whereas, in MaxHeap, the parent node value must be greater than its child nodes.

The deletion/extraction of elements occur only at the topmost node i.e., the root node. Hence for a minheap, the extracted node will always be a node with least value and for maxheap, the extracted node will always be a node with maximum value.

**Representation**:

Heap can be represented by arrays and lists; we will see the array representation here. We consider an array with a capacity and then go on inserting the elements in such a way that the arrays arrange their elements according to their priority.

Now, not always we will be inserting in the same order of priority. In such a case, the Heap percolates its property down from a node that does not follow that property. This is called percolating down or Heapifying. Don’t worry we will discuss it clearly after this section.**Also, understand 10 Programming Languages With Data Structures & Algorithms**

**Code Implementation**:

```
struct heap{
int capacity; //capacity of the initial heap
int heap_type; // 0 – minheap 1- maxheap
int *arr; //array used to store the elements
int count; //number of elements currently in the heap
};
struct heap *CreateHeap(int capacity,int heap_type){
struct heap *h = new heap();
h->capacity = capacity;
h->heap_type = heap_type;
h->arr = new int[h->capacity];
h->count = 0;
return h;
}
//finding the child of ith node and parent.
The ith node will have at most 2 children at 2i+1 and 2i+2 in a 1 based indexed array.
The ith node will have its parent at (i-1)/2.
int leftchild(struct heap *h,int i){
int left = 2*i+1'
if(left>=h->count) return -1;
return left;
}
int rightchild(struct heap *h,int i){
int right = 2*i+1'
if(right>=h->count) return -1;
return right;
}
int parent(struct heap *h,int i){
if(i<=0 && i>=h->count)return -1;
return (i-1)/2;
}
//Getting max element from maxheap or min element from minheap
int getMax(struct heap *h){
if(h->count == 0) return -1;
return h->arr[0]; //its always the first element in the heap array
}
```

**Heapifying an element**

As discussed above if we insert an element whose priority is not in the order of its insertion then the whole heap may dissatisfy the heap property and hence this has to be rectified. The process of rectifying and restoring its property is called heapify. Let us have an index where the heap property is not valid then we start from that node and move till the bottom of the tree heapifying each dissatisfying node below it.

**Heapify pproach**

For a current node, we find the largest of its children and swap it with our current element (for max heap). We then move to the swapped node below and repeat the same process until all the nodes are heapified.

Let us see an example:

We swap this node 1 with node 10 as it has the highest value among its children. And we percolate down to heapify all elements below it. Final heap will become

**Code Implementation**:

```
void heapify(struct heap *h,int i){
int l,r,max,temp;
l = leftchild(h,i);
r = rightchild(h,i);
if(l!=-1 && h->arr[l] > h->arr[i])
max = l; //finding the max child
else
max = i;
if(r!=-1 && h->arr[r] > h->arr[max])
max = r; //finding the max child
if(max != i){ //if child found
int temp = h->arr[i];
h->arr[i] = h->arr[max];
h->arr[max] = temp;
}
heapify(h,max); //recursively moving to the next child
}
```

Now we have seen all the prerequisites of this heap data structure. For implementation, we can create our own user-defined class for this, or we can simply use STL in C++. In C++ STL the default priority queue heap is called max heap. For converting it into min-heap we have to define our comparison function.

**Difference Between Min Heap & Max Heap: **

**Min Heap**

- The top node/root node will always have a minimum value.
- Extracting an element from the priority queue will always give the minimum among all the current values stored in the heap.
- Inserting and deletion operation takes time.

**Max Heap**

- The top node/root node will always have a maximum value.
- Extracting an element from the priority queue will always give the mum among all the current values stored in the heap.
- Inserting and deletion operation takes
**log***(n)*

**Creating the max and min heaps with C++ STL**

```
#include <bits/stdc++.h>
using namespace std;
//priority queue or heap data structure using C++ STL
int main() {
// your code goes here
priority_queue<int> pq; //default max heap is created
pq.push(5);
pq.push(2);
pq.push(3);
pq.push(1);
pq.push(6);
//printing will be done in descending order
while(!pq.empty()){
cout<<pq.top()<<endl;
pq.pop();
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
//priority queue or heap data structure using C++ STL
int main() {
// your code goes here
priority_queue<int, vector<int>, greater<int> > pq; //compare function min heap is created
pq.push(5);
pq.push(2);
pq.push(3);
pq.push(1);
pq.push(6);
//printing will be done in ascending order
while(!pq.empty()){
cout<<pq.top()<<endl;
pq.pop();
}
return 0;
}
```

**Time Complexity**

While dealing with Heaps we have to take care that this does increase the space complexity by**.** Hence when we have limited space, we should avoid using this and might compromise our time complexity. Hence, we can see that **Heap/ Priority queue** data structure is a very powerful tool used in very popular algorithms to reduce the time complexity by a significant amount by using simple balancing of the tree property.

## Frequently Asked Questions

**How do I start learning DS and algorithms?**

After mastering one programming language, the next step is to use that language to implement data structures. Starting from linear data structures, move towards advanced topics but don’t just study topics theoretically. Simultaneous implementation is important. To get a defined path, taking an online course is recommended.

**Which language is best for DS and Algo?**

Most competitive programmers use C++ because of its efficiency for DSA. That being said, the language is just a medium and any language that you are affluent with is appropriate for you to implement DSA.

**How do I prepare for DS and algorithms?**

Practicing as many problems as you can find and that too consistently is the key to mastering DSA. Online platforms like CodeStudio, LeetCode, Codeforces have a pool of problems of all types, practicing which will help you master DSA.

**How long will it take to learn data structures and algorithms?**

On a generic note, mastering DSA will take around 3-4 months. A good foundation is important so do not rush through it, be patient and take your time because the pace of learning is different for every learner.

## Key Takeaways

Hope this article is useful to aspire programmers and developers. To read more such articles, visit our blog section and explore our courses too!

**By Aniruddha Guin**

## Leave a Reply