Working with a Priority Queue of Pairs in C++

The standard queue is a container adaptor that provides the functionality of a queue, adhering to the first-in, first-out (FIFO) data structure. This class template serves as a wrapper to the underlying container, offering a specific set of functions. The queue operates by pushing elements onto the back of the underlying container and popping them from the front. The standard queue uses an underlying container to store its elements. The container must meet the requirements of a Sequence Container and provide the following functions with their standard semantics:

1. back(),
2. front(),
3. push_back(),
4. and pop_front().

mudamasters

In C++, a priority queue is a container adapter that provides a queue-like interface but allows elements to be processed based on their priorities. By default, the elements in a priority queue are ordered based on a comparison function or operator, with the highest priority element always at the front.

Queues are of four types — linear, circular, dequeue, and priority. As the title suggests, this article deals with priority queues of Pairs.

Priority Queue of Pairs:

In a priority queue, elements are ordered based on their weight or value. For example, if we push the elements 23, 75, 17, 99, and 5 into a priority queue, the output will be 99, 75, 23, 17, 5 when printed.

In a priority queue of pairs, pairs of elements are pushed into the queue. For instance, if we push the pairs (23, 10), (75, 19), (17, 74), (99, 18), and (5, 37) into the priority queue, the queue will be ordered based on the first element of each pair, and the output will be (99, 18), (75, 19), (23, 10), (17, 74), and (5, 37) when printed.

To create a priority queue to store pairs of frequencies and elements, we need to define the type of elements stored in the queue as std::pair<int, int>. This pair represents the frequency and element values. The first element in the pair will represent the frequency, and the second element will represent the actual element value.

#include <queue>
#include <utility>

// Creating a priority queue of pairs
std::priority_queue<std::pair<int, int>> pq;

The above code declares a priority queue pq that will store pairs of frequencies and elements. The std::pair<int, int> specifies the type of each element in the priority queue.

Insertion of Element:
To insert elements into the priority queue, you can use the push function and provide the pair of frequencies and elements as arguments.

pq.push(std::make_pair(frequency, element));

The push function adds the pair into the priority queue based on the specified priority order. The element with the highest frequency will be placed at the front of the queue.

Access the top element:
To access the top element of the priority queue, we can use the top function, which returns a reference to the pair with the highest priority.

std::pair<int, int> topPair = pq.top();
int frequency = topPair.first;
int element = topPair.second;

The top function retrieves the top element of the priority queue. In this case, it retrieves the pair with the highest frequency and assigns the frequency and element values to separate variables.

Removal of Element:
To remove the top element from the priority queue, you can use the pop function.

pq.pop();

The pop function removes the top element from the priority queue, making the next highest priority element the new top.

Priority Queues of Pairs With Ordering:

Priority queues of pairs are a specific type of priority queue, and they can be further categorized into two types based on which element in the pair is used for prioritizing. These types are:

(i) Priority queue of pairs ordered by the first element in the pair
(ii) Priority queue of pairs ordered by the second element in the pair

Priority Queue of Pairs Ordered by the First Element (Max Heap):
To understand the concept of a priority queue of pairs ordered by the first element, let’s revisit the example with pairs (23, 10), (75, 19), (17, 74), (99, 18), and (5, 37). When prioritizing based on the first element of each pair, the output on printing the queue will be (99, 18), (75, 19), (23, 10), (17, 74), and (5, 37).

Now, let’s attempt to write the CPP code for this type of priority queue.

Priority Queue of Pairs Ordered by the Second Element (Max Heap):
If you guessed that pairs ordered by the second element prioritize based on the second element in the pair, you are correct! To illustrate this, let’s consider the example with pairs (23, 10), (75, 19), (17, 74), (99, 18), and (5, 37).

When ordering by the second element, the output will be (17, 74), (5, 37), (75, 19), (99, 18), (23, 10).

Fundamentals: Priority Queue

The priority queue is a container adaptor that offers constant time access to the largest (by default) element, with the trade-off of logarithmic insertion and extraction. A user-defined Compare can be used to alter the ordering, for example, employing std::greater<T> would result in the smallest element being at the top(). Using a priority_queue is akin to managing a heap within a random access container, with the advantage of avoiding accidental invalidation of the heap.

A priority queue is a type of queue where each element has an associated priority. The priority of an element determines its order in the queue, with higher priority elements being placed at the front and lower priority elements being placed at the rear. Thus, the element with the highest priority is always at the front of the priority queue.

Priority queues provide two main operations: insertion and removal. When an element is inserted into a priority queue, it is placed at the appropriate position based on its priority. When an element is removed from the priority queue, the highest priority element is removed from the front.

Conclusion

Creating a priority queue to store pairs of frequencies and elements in C++ can be invaluable for solving various problems that require prioritizing elements based on frequency. By mastering the creation and manipulation of priority queues of pairs, you can effectively process and retrieve elements with the highest priority.

In conclusion, working with a priority queue of pairs in C++ equips us with a powerful tool for efficiently managing and processing elements based on their priority, providing a valuable skill for solving a wide range of programming problems.