'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before', 'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before',
Update appNew update is available. Click here to update.
Last Updated: Dec 26, 2023

Difference Between Min Heap and Max Heap

Author
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Recommended Topic, floyd's algorithm

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.

MaxHeap

MinHeap

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.
 

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 approach

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. Hence when we have limited space, we should avoid using this and might compromise our time complexity. Hence, we can see that the 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.

Also Read, binary search algorithm

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.

Conclusion

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

Recommended Reading:

Difference Between List and Set

Previous article
Difference between array and stack
Next article
Stable Sorting Algorithm
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass