Implementing Priority Queue in C++

Introduction

In this lab, we will learn about the basic functionality of the Priority Queue in C++ programming language. Priority Queue is a container in C++ STL (Standard Template Library) that allows you to insert and remove elements according to their priority. The element with the highest priority is always placed at the front of the queue. When an element is removed from the queue, the priority queue automatically takes care of inserting the next highest priority element at its correct position.

Include the Required Libraries

We will create a new file named main.cpp in the ~/project directory using the following command:

touch ~/project/main.cpp

We first need to include the required libraries for our program to work properly. In this program, we will be using iostream and bits/stdc++.h libraries.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

Define the show Function

The show function is used to display all the elements present in the priority queue. The function takes a priority queue object as an argument, and it copies the queue into another to maintain the original priority queue. After that, it prints all the elements present in the priority queue by iterating over it.

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top(); //printing the top most element
        pq.pop();                 //deleting the top most element to move to the next
    }
    cout << endl;
}

Implement the Main Function

The main function is where all the action happens. We first declare an integer variable i. Then we create a priority queue of integers names q. We then add some integers to the priority queue using the push function.

After that, we display the elements present in the priority queue using the show function. We then use the size function to display the number of elements present in the queue, and we use the top function to display the element with the highest priority.

Next, we use the pop function to remove the element with the highest priority and display the updated priority queue using the show function.

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

Final Code

You can use the following code to implement Priority Queue in C++:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top();
        pq.pop();
    }
    cout << endl;
}

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

Save the above code in ~/project/main.cpp. To compile and run this code, use the following commands:

g++ main.cpp -o main && ./main

Summary

In this lab, we learned about the basic concepts of Priority Queue in C++. We also saw how to declare and initialize a priority queue and how to add, remove and display elements from it. We hope you found this tutorial useful.

Implementing Priority Queue