DEV Community

cybo-neutron
cybo-neutron

Posted on

1 1

Priority Queue in C++

In this article we will be exploring different methods of creating a priority queue in C++ and modifying it according to our use case.

By default priority queue in C++ implements max heap. That means that the top most element will always be the greatest of all numbers present in the priority queue.

These are some of the member functions of priority queue.

Member functions

  1. Element Access
    • top -> Returns the top element of the priority_queue
  2. Capacity
    • empty -> returns true if empty
    • size -> size of priority_queue
  3. Modifiers
    • push -> inserts element
    • emplace -> insert element
    • pop -> removes the top element

Simple example of priority queue

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<int> pq;
    // inserting elements
    pq.push(1);
    pq.push(4);
    pq.push(0);

    // Printing the elements of priority queue untill the priority queue is not empty
    while (!pq.empty()) 
    {
        int top = pq.top(); // accessing the top element of priority queue
        pq.pop();           // removing the top element of the priority queue
        std::cout << top << " ";
    }

    /*
    The elements will be printed in descending order as the priority queue by default implement max-heap.
    Output : 
        4 1 0

    */
}
Enter fullscreen mode Exit fullscreen mode

Creating a Priority Queue

  1. Creating empty priority queue

    #include <queue>
    int main()
    {
        std::priority_queue<int> pq;
    
    }
    
  2. Creating a priority queue from a vector

    std::vector<int> v{5, 6, 3, 9};
    
    std::priority_queue<int> pq(v.begin(), v.end());
    
  3. Creating a min-heap priority queue

    std::vector<int> v{5, 6, 3, 9};
    
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq(v.begin(), v.end());
    

Creating priority queue with custom comparator

In this section we will explore all sort of different techniques of creating a priority queue using our own custom comparator.

The third template parameter should be a function pointer or a class with () overloaded.

  1. Declaring a compare function
    int comp(int a, int b)
    {
        return a < b;
    }

    std::vector<int> v{5, 6, 3, 9};
    //Priority queue using vector
    std::priority_queue<int, std::vector<int>, decltype(&comp)> pq(v.begin(), v.end(), comp);
    //Declaring the type of function yourself. -> bool (*)(int, int)
    std::priority_queue<int, std::vector<int>, bool (*)(int, int)> pq(v.begin(), v.end(), comp);
    //Declaring using the function class template
    std::priority_queue<int, std::vector<int>, std::function<bool(int, int)>> pq(v.begin(), v.end(), comp);

    //Empty priority queue with comp as comparator
    std::priority_queue<int, std::vector<int>, decltype(&comp)> pq2(comp);

Enter fullscreen mode Exit fullscreen mode
  1. Declaring compare lambda function

    NOTE : In decltype(comp) we no longer require the & operator.

    auto comp = [](int a, int b)
    {
        return a < b;
    };
    
    std::vector<int> v{5, 6, 3, 9};
    //Using decltype
    std::priority_queue<int, std::vector<int>, decltype(comp)> pq(v.begin(), v.end(), comp);
    //Using function pointer
    std::priority_queue<int, std::vector<int>, bool (*)(int, int)> pq(v.begin(), v.end(), comp);
    //Using function class template
    std::priority_queue<int, std::vector<int>, std::function<bool(int, int)>> pq(v.begin(), v.end(), comp);
    
    std::priority_queue<int, std::vector<int>, decltype(comp)> pq2(comp);
    
  2. Declaring using a compare class

    Declare the class like shown below.

    NOTE : You can also use struct in place of class.

    class Compare
    {
    public:
        bool operator()(int a, int b)
        {
            return a < b;
        }
    };
    

    Use the compare class while declaring the priority queue

    std::priority_queue<int, std::vector<int>, Compare> pq(v.begin(), v.end());
    

Now lets take an example of its use case.
We want to take out students from the priority queue based on their age.

#include <iostream>
#include <queue>
#include <vector>

struct Student
{
    std::string name;
    int age;
    int rollno;

    void print()
    {
        std::cout << name << " | " << age << " | " << rollno << "\n";
    }
};

class Compare
{
public:
    bool operator()(Student &a, Student &b)
    {
        return a.age > b.age;
    }
};

int main()
{
    std::vector<Student> students{
        Student{"Naruto", 18, 100},
        Student{"Sasuke", 19, 120},
        Student{"Rock Lee", 17, 077}};

    std::priority_queue<Student, std::vector<Student>, Compare> pq(students.begin(), students.end());

    while (!pq.empty())
    {
        auto top = pq.top();
        pq.pop();
        top.print();
    }
}
#include <iostream>
#include <queue>
#include <vector>

struct Student
{
    std::string name;
    int age;
    int rollno;

    void print()
    {
        std::cout << name << " | " << age << " | " << rollno << "\n";
    }
};

class Compare
{
public:
    bool operator()(Student &a, Student &b)
    {
        return a.age > b.age;
    }
};

int main()
{
    std::vector<Student> students{
        Student{"Naruto", 18, 100},
        Student{"Sasuke", 19, 120},
        Student{"Rock Lee", 17, 077}};

    std::priority_queue<Student, std::vector<Student>, Compare> pq(students.begin(), students.end());

    while (!pq.empty())
    {
        auto top = pq.top();
        pq.pop();
        top.print();
    }
}

/* Output

Rock Lee | 17 | 63
Naruto | 18 | 100
Sasuke | 19 | 120

*/

Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Image of Stellar post

How a Hackathon Win Led to My Startup Getting Funded

In this episode, you'll see:

  • The hackathon wins that sparked the journey.
  • The moment José and Joseph decided to go all-in.
  • Building a working prototype on Stellar.
  • Using the PassKeys feature of Soroban.
  • Getting funded via the Stellar Community Fund.

Watch the video 🎥

👋 Kindness is contagious

Dive into this thoughtful article, cherished within the supportive DEV Community. Coders of every background are encouraged to share and grow our collective expertise.

A genuine "thank you" can brighten someone’s day—drop your appreciation in the comments below!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found value here? A quick thank you to the author makes a big difference.

Okay