C++ Standard Template Library (STL) – [Priority queue]

In the last post we discussed about C++ Standard Template Library (STL) Linked List. In this post we would 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 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:

https://ideone.com/4qn1sJ

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:

https://ideone.com/HXsoAF

Leave a Reply

Your email address will not be published.