Heap: Max Heap and Min heap using Priority Queue

In this chapter we will learn about priority queue.

Priority Queue is a data structure, where each element is associated with a priority value.

Elements are inserted based on priority. Highest priority element will be dequeued first.

Priority Queue can be represented as form of an array, heap DS, linked list.

Amoung those, heap data structure provides an efficient implementation of priority queues.

We can use Priority Queue to create MaxHeap or MinHeap.

Max Heap Example using Priority Queue

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{

	priority_queue<int> pq;

   	pq.push(6);
   	pq.push(1);
   	pq.push(2);
   	pq.push(5);
   	pq.push(7);
   	pq.push(9);
   	pq.push(3);

   	cout<<"The top element is "<<pq.top();
}

Output;

The top element is 9

Here according to Max Heap, the root element will always be the largest element

Min Heap Example using Priority Queue

We can use PQ to create min heap also.

Syntax for min heap:

priority_queue <object_type, vector<object_type>, greater<object_type>> variable_name;

Here :

object_type: It is the type of object like int, string, etc.

vector<object_type> is used to store the elements.

greater<object_type> is a comparator what will ensure that the smallest element is always at the top.

By default less<object_type> is used for the max heap

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{

	priority_queue <int, vector<int>, greater<int>> pq;

   	pq.push(6);
   	pq.push(1);
   	pq.push(2);
   	pq.push(5);
   	pq.push(7);
   	pq.push(9);
   	pq.push(3);

   	cout<<"The min element is "<<pq.top();
}

Output;

The min element is 1

Here according to min Heap, the root element will always be the smallest element