In the last post we discussed about C++ Standard Template Library (STL) Linked List. In this post we will learn about STL Priority queue and using it as Max/Min Heap.
Priority Queue
A priority queue is a data structure for maintaining a set of elements having an associated value. Priority Queue supports the following operations:
Note: For using priority queue, you need to include the header file “queue”
Max-Heap using priority Queue
Insert (Q, x) 1. Q.push(x) Max (Q) 1. return Q.top() Extract-Max (Q) 1. x = Q.top() 2. Q.pop() 3. return x
Code Implementation
//
// main.cpp
// Priority Queue
//
// Created by Himanshu on 19/09/21.
//
#include <iostream>
#include <queue>
using namespace std;
int main () {
priority_queue<int> pq;
cout<<"Insert Q(x) {30, 100, 25, 40}"<<endl;
pq.push(30);
pq.push(100);
pq.push(25);
pq.push(40);
cout<<"Maximum Element (Q)"<<endl;
cout<<pq.top()<<endl;
cout<<"Maximum Element (Q) after Extract-Max (Q)"<<endl;
pq.pop();
cout<<pq.top()<<endl;
cout <<"Extracting out elements..."<<endl;
while (!pq.empty()) {
cout<< pq.top()<<" ";
pq.pop();
}
cout<<endl;
if (pq.empty()) {
cout<<"Priority queue is empty"<<endl;
} else {
cout<<"Priority queue is not empty"<<endl;
}
return 0;
}
Output
Insert Q(x) {30, 100, 25, 40}
Maximum Element (Q)
100
Maximum Element (Q) after Extract-Max (Q)
40
Extracting out elements...
40 30 25
Priority queue is empty
Here’s a working example: Ideone
Min-Heap using priority Queue
To make Min-Heap using priority queue, initialise priority queue as follows:
priority_queue<int, vector<int>, greater <int> > Q; Insert (Q, x) 1. Q.push(x) Min (Q) 1. return Q.top() Extract-Min (Q) 1. x = Q.top() 2. Q.pop() 3. return x
Code Implementation
//
// main.cpp
// Priority Queue (Min Heap)
//
// Created by Himanshu on 19/09/21.
//
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
int main () {
priority_queue<int, vector< int>, greater <int> > pq;
cout<<"Insert Q(x) {30, 100, 25, 40}"<<endl;
pq.push(30);
pq.push(100);
pq.push(25);
pq.push(40);
cout<<"Minimum Element (Q)"<<endl;
cout<<pq.top()<<endl;
cout<<"Minimum Element (Q) after Extract-Min (Q)"<<endl;
pq.pop();
cout<<pq.top()<<endl;
cout <<"Extracting out elements..."<<endl;
while (!pq.empty()) {
cout<< pq.top()<<" ";
pq.pop();
}
cout<<endl;
if (pq.empty()) {
cout<<"Priority queue is empty"<<endl;
} else {
cout<<"Priority queue is not empty"<<endl;
}
return 0;
}
Output
Insert Q(x) {30, 100, 25, 40}
Minimum Element (Q)
25
Minimum Element (Q) after Extract-Min (Q)
30
Extracting out elements...
30 40 100
Priority queue is empty
Here’s a working example: Ideone
One thought on “C++ Standard Template Library (STL) – [Priority queue]”