Minheap & Maxheap in Data Structures

Minheap & Maxheap in Data Structures
Minheap & Maxheap in Data Structures

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.

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 list; 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 its 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 which does not follow that property. This is called percolating down or heapifying. Don’t worry we will discuss it clearly after this section.

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 it’s property is called heapify. Let we 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.

Approach

blog banner 1

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

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:  , where n is the number of elements being inserted in both the cases.

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.

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

By Aniruddha Guin