Minheap & Maxheap in Data Structures

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) time.

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

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