C++ Priority Queue

Introduction to C++ Priority Queue

A priority queue is an abstract data type in C++ that stores elements in a specific order based on their priority. The elements with higher priority are dequeued first. In other words, the element with the highest priority is always at the front of the queue.

C++ provides a built-in container called priority_queue to implement a priority queue. It is part of the Standard Template Library (STL) and is defined in the <queue> header.

Creating a Priority Queue

To use a priority queue in C++, you need to include the <queue> header and declare an instance of the priority_queue class with the desired data type. Here’s an example of creating a priority queue of integers:

#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    return 0;
}

In the above code, we have created a priority queue named pq of type int.

Inserting Elements into a Priority Queue

To insert elements into a priority queue, you can use the push() function. The elements are inserted in such a way that the highest priority element is always at the front of the queue. Here’s an example:

#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    
    pq.push(5);
    pq.push(10);
    pq.push(3);
    
    return 0;
}

In the above code, we have inserted three integers (5, 10, and 3) into the priority queue pq using the push() function. The elements are automatically arranged in descending order based on their values.

Accessing the Top Element of a Priority Queue

To access the element with the highest priority (i.e., the element at the front of the priority queue), you can use the top() function. Here’s an example:

#include <queue>
#include <iostream>
using namespace std;

int main() {
    priority_queue<int> pq;
    
    pq.push(5);
    pq.push(10);
    pq.push(3);
    
    cout << "Top element: " << pq.top() << endl;
    
    return 0;
}

In the above code, we have accessed the top element of the priority queue pq using the top() function. The output will be:

Top element: 10

Removing Elements from a Priority Queue

To remove the element with the highest priority from a priority queue, you can use the pop() function. Here’s an example:

#include <queue>
#include <iostream>
using namespace std;

int main() {
    priority_queue<int> pq;
    
    pq.push(5);
    pq.push(10);
    pq.push(3);
    
    cout << "Top element: " << pq.top() << endl;
    
    pq.pop();
    
    cout << "New top element: " << pq.top() << endl;
    
    return 0;
}

In the above code, we have removed the top element from the priority queue pq using the pop() function. After removing the top element, the next highest priority element becomes the new top element. The output will be:

Top element: 10
New top element: 5

Customizing the Priority Queue

The default behavior of the priority_queue in C++ is to arrange elements in descending order. However, you can customize the ordering by providing a comparison function or using a custom data type that overloads the comparison operator (<).

Here’s an example of creating a priority queue of strings in ascending order:

#include <queue>
#include <iostream>
using namespace std;

bool compareStrings(string s1, string s2) {
    return s1.length() > s2.length();
}

int main() {
    priority_queue<string, vector<string>, decltype(compareStrings)*> pq(compareStrings);
    
    pq.push("apple");
    pq.push("banana");
    pq.push("cherry");
    
    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }
    
    return 0;
}

In the above code, we have created a priority queue named pq of type string. We have also defined a comparison function named compareStrings that compares the length of two strings. The priority queue is initialized with this comparison function, which arranges the strings in ascending order based on their lengths.

The output of the above code will be:

apple
cherry
banana

Conclusion

In this article, we have explored the concept of a priority queue in C++ and how to use the priority_queue class from the Standard Template Library (STL). We have seen examples of creating a priority queue, inserting elements, accessing the top element, and removing elements based on their priority. Additionally, we have learned how to customize the priority queue order using comparison functions or overloaded comparison operators.

By understanding and utilizing the C++ priority queue, you can efficiently manage and process elements based on their priority in various applications and algorithms.