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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | //// 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | //// 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]”