C++ Priority Queue With Custom Comparator

Priority queues are indeed a unique data type. They are supported by heaps (a form of a binary tree), but they have been utilized similarly as queues. What distinguishes a priority queue from a regular queue would be that it keeps its sorting arrangement in O(logN) duration even when adding or deleting new members. With rudimentary data types like numbers and strings, using a priority queue seems to be the simplest. Priority queues for customized types are feasible, as is the ability to construct a custom sort pattern for basic kinds. Using priority queues, you may use a customized comparator, like ordering vectors, to describe how entries in the priority queue can be sorted. In C++, this is typically finished with only a struct. However, lambda statements are faster to construct and allow you to access variables beyond the scope (which is complex to make sure with structs). So, within this guide, we will be discussing the priority queue example with the customer comparator.

Example:

Let’s get started with the example of using a priority queue with the custom comparator in C++. So the terminal shell has to be opened with Ctrl+Alt+T short way. The C++ file needs to be created in the shell using the “touch” instruction of Ubuntu. It’s quite easy to do so. After that, this file must be opened within some editor to make code. You can have vim, text, or nano editor. We utilize the “nano” editor here for quick editing and updating.

$ touch queue.cc
$ nano queue.cc

So, the empty c++ file will be opened on your terminal screen within the nano editor. It’s time to add some header libraries within its start to make our code work properly. Therefore, we used the “#include” sign with each header. The “iostream” header is used to make use of the input-output stream. The “vector” header is cast-off to use the vector data structure. The “unordered_map” header has been used to create a map for the values of a vector in quantities. The “queue” header file is here to use the priority queue and its related data functions. We started the main () method after the “std” standard namespace usage, we have started the main() method. We have created a vector data structure named “color” of string type to hold string values. While the vector object “color” has been using the push_back() function to add some color names in the vector, i.e., Red, Green, Blue, White, and Black.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
int main()
{
cout << "Starting...\n";
vector<string> color;
color.push_back("Red");
color.push_back("Green");
color.push_back("Blue");
color.push_back("White");
color.push_back("Black");

After creating a vector object, we have to create a map structure using the”unordered_map” keyword. The object for this map is “m,” and it contains string and integer parameters. The map is created to bind the integer quantity with the string vector, so the integer type value is assigned to string values of a vector “color” individually.

Unordered_map<string, int>m;
m["Red"] = 2;
m["Green"] = 4;
m["Blue"] = 6;
m["White"] = 8;
m["Black"] = 10;

Here comes the custom comparator declared as variable “cmp” with the keyword “auto.” The auto keyword is used to get back the result of any type without defining it. The “if” statement is used to check whether the quantity of a left map value is equal to the quantity of a right map value or not. If so, it will return that the left side character is greater than the right side character of a string to the “cmp” variable. If they are not equal, it will return that the right-side quantity value is greater than the left-side quantity value of a string through a map. This is sorting the quantity in descending order while the string name is ordered in ascending order.

auto cmp = [&](string& l, string& r) {
if(m[le] == m[r]) {
return l > r; }
return m[r] > m[l];
};

Now, it’s time to create a priority queue and add all the colors utilizing the vector. So, the priority queue has been generated using the string type vector, and the declaration type has been set as got from the comp variable. The PQ is the priority queue object. The “for” loop is here to push each color to the priority queue “PQ” via the push() function.

priority_queue<string, vector<string>, decltype(cmp)> pq(cmp);
for(const string& clr: color) {
pq.push(clr);
}

The “while” loop continues to be executed until the queue is not empty and adds each string from it to the string “clr”. That particular value would be popped up and be displayed on the shell. Our program code is completed here and ready to be executed.

while(!pq.empty()){
string fruit = pq.top();
pq.pop();
cout << fruit << " " << m[fruit] << endl;
}
cout << "Ending...\n";
return 0;
}

The compilation is quite successful. More than that, all the string values of the vector have been displayed on the shell along with their quantities that are being mapped through “map.” You can see that the quantity order is descending in our case.

$ g++ queue.cc
$ ./a.out

Conclusion:

This was all about the simple example of a Priority queue with a custom comparator in C++. We have discussed it within a single example in detail by maintaining a simple and easiest way. We have added the code in the form of chunks that helps the readers to understand it well.

C++ Priority Queue With Custom Comparator

Example:

Conclusion:

About the author

Omar Farooq