Difference Between Min Heap and Max Heap

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