Menu
I have a basic doubt, in that I am trying to figure out the versatility of priority_queue STL in C++.
I know that priority queue by default is actually a max_heap. I also am aware that it can be modified in the following way to create a min_heap:
priority_queue <int, vector<int>, greater<int> > pq;
What I aim to achieve, is that I want to create a priority_queue <pair <int,int> pq, such that heap is a max_heap for the first element in the pair, and it is a min_heap for the second element in the pair. For example, on inserting the following pairs:
(2,4) (1,5) (1,6)
The output when elements are displayed is as follows:
(2,4)
(1,5)
(1,6)
By default, the output would have been:
(2,4)
(1,6)
(1,5)
Is it possible? If yes, then how?
Thank you in advance.
370
To access the elements of the pair, use variable name followed by dot operator followed by the keyword 'first' or 'second', these are public members of class pair.
Step 1: Create a class where a custom comparator is made. Step 2: Define a priority queue that stores a pair of integers. Step 3: Take the number of pairs and the elements in the queue as input from the user. Step 4: Store the pair of integers in the priority queue using a loop.
The first element of pair Arr1 is sorted with the pair elements of pair “Arr2”. In the main function, we have initialized the values for pair array “Arr1” and pair array “Arr2”. These sorted arrays and the original pairs array will be displayed by using the cout command.
In order to create a priority queue in C++, we first need to include the queue header file. Once we import this file, we can create a priority_queue using the following syntax: priority_queue<type> pq; Here, type indicates the data type we want to store in the priority queue.
You can write a custom comparison that compares the first element with operator<, and the second element with operator>.
struct less_then_greater {
template<typename T, typename U>
bool operator()(T const& lhs, U const& rhs) const {
if (lhs.first < rhs.first) return true;
if (rhs.first < lhs.first) return false;
return lhs.second > lhs.second;
}
};
std::priority_queue<std::pair<int, int>,
std::vector<std::pair<int, int>>,
less_then_greater
> pq;
Note that this isn't creating a min-heap for one, and a max-heap for the other. But based on the output you describe, I don't think that's what you were really asking for.
52
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
