How can I create Min stl priority_queue?
C++StlPriority QueueC++ Problem Overview
The default stl priority queue is a Max one (Top function returns the largest element).
Say, for simplicity, that it is a priority queue of int values.
C++ Solutions
Solution 1 - C++
Use std::greater as the comparison function:
std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;
Solution 2 - C++
One way would be to define a suitable comparator with which to operate on the ordinary priority queue, such that its priority gets reversed:
#include <iostream>
#include <queue>
using namespace std;
struct compare
{
bool operator()(const int& l, const int& r)
{
return l > r;
}
};
int main()
{
priority_queue<int,vector<int>, compare > pq;
pq.push(3);
pq.push(5);
pq.push(1);
pq.push(8);
while ( !pq.empty() )
{
cout << pq.top() << endl;
pq.pop();
}
cin.get();
}
Which would output 1, 3, 5, 8 respectively.
Some examples of using priority queues via STL and Sedgewick's implementations are given here.
Solution 3 - C++
The third template parameter for priority_queue is the comparator. Set it to use greater.
e.g.
std::priority_queue<int, std::vector<int>, std::greater<int> > max_queue;
You'll need #include <functional> for std::greater.
Solution 4 - C++
You can do it in multiple ways:
-
Using
greateras comparison function :#include
using namespace std;
int main() { priority_queue
>pq; pq.push(1); pq.push(2); pq.push(3); while(!pq.empty()) { int r = pq.top(); pq.pop(); cout<<r<< " "; } return 0;}
-
Inserting values by changing their sign (using minus (-) for positive number and using plus (+) for negative number :
int main() { priority_queue
pq2; pq2.push(-1); //for +1 pq2.push(-2); //for +2 pq2.push(-3); //for +3 pq2.push(4); //for -4 while(!pq2.empty()) { int r = pq2.top(); pq2.pop(); cout<<-r<<" "; } return 0;}
-
Using custom structure or class :
struct compare { bool operator()(const int & a, const int & b) { return a>b; } };
int main() {
priority_queue<int,vector<int>,compare> pq; pq.push(1); pq.push(2); pq.push(3); while(!pq.empty()) { int r = pq.top(); pq.pop(); cout<<r<<" "; } return 0;}
-
Using custom structure or class you can use priority_queue in any order. Suppose, we want to sort people in descending order according to their salary and if tie then according to their age.
struct people { int age,salary; }; struct compare{ bool operator()(const people & a, const people & b) { if(a.salary==b.salary) { return a.age>b.age; } else { return a.salary>b.salary; } } }; int main() { priority_queue<people,vector<people>,compare> pq; people person1,person2,person3; person1.salary=100; person1.age = 50; person2.salary=80; person2.age = 40; person3.salary = 100; person3.age=40; pq.push(person1); pq.push(person2); pq.push(person3); while(!pq.empty()) { people r = pq.top(); pq.pop(); cout<<r.salary<<" "<<r.age<<endl; } -
Same result can be obtained by operator overloading :
struct people { int age,salary; bool operator< (const people & p)const { if(salary==p.salary) { return age>p.age; } else { return salary>p.salary; } }};In main function :
priority_queue<people> pq; people person1,person2,person3; person1.salary=100; person1.age = 50; person2.salary=80; person2.age = 40; person3.salary = 100; person3.age=40; pq.push(person1); pq.push(person2); pq.push(person3); while(!pq.empty()) { people r = pq.top(); pq.pop(); cout<<r.salary<<" "<<r.age<<endl; }
Solution 5 - C++
In C++11 you could also create an alias for convenience:
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
And use it like this:
min_heap<int> my_heap;
Solution 6 - C++
One Way to solve this problem is, push the negative of each element in the priority_queue so the largest element will become the smallest element. At the time of making pop operation, take the negation of each element.
#include<bits/stdc++.h>
using namespace std;
int main(){
priority_queue<int> pq;
int i;
// push the negative of each element in priority_queue, so the largest number will become the smallest number
for (int i = 0; i < 5; i++)
{
cin>>j;
pq.push(j*-1);
}
for (int i = 0; i < 5; i++)
{
cout<<(-1)*pq.top()<<endl;
pq.pop();
}
}
Solution 7 - C++
Based on above all answers I created an example code for how to create priority queue. Note: It works C++11 and above compilers
#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
using namespace std;
// template for prirority Q
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
template<class T> using max_heap = priority_queue<T, std::vector<T>>;
const int RANGE = 1000;
vector<int> get_sample_data(int size);
int main(){
int n;
cout << "Enter number of elements N = " ; cin >> n;
vector<int> dataset = get_sample_data(n);
max_heap<int> max_pq;
min_heap<int> min_pq;
// Push data to Priority Queue
for(int i: dataset){
max_pq.push(i);
min_pq.push(i);
}
while(!max_pq.empty() && !min_pq.empty()){
cout << setw(10) << min_pq.top()<< " | " << max_pq.top() << endl;
min_pq.pop();
max_pq.pop();
}
}
vector<int> get_sample_data(int size){
srand(time(NULL));
vector<int> dataset;
for(int i=0; i<size; i++){
dataset.push_back(rand()%RANGE);
}
return dataset;
}
Output of Above code
Enter number of elements N = 4
33 | 535
49 | 411
411 | 49
535 | 33
Solution 8 - C++
We can do this using several ways.
Using template comparator parameter
int main()
{
priority_queue<int, vector<int>, greater<int> > pq;
pq.push(40);
pq.push(320);
pq.push(42);
pq.push(65);
pq.push(12);
cout<<pq.top()<<endl;
return 0;
}
Using used defined compartor class
struct comp
{
bool operator () (int lhs, int rhs)
{
return lhs > rhs;
}
};
int main()
{
priority_queue<int, vector<int>, comp> pq;
pq.push(40);
pq.push(320);
pq.push(42);
pq.push(65);
pq.push(12);
cout<<pq.top()<<endl;
return 0;
}
Solution 9 - C++
Multiply values with -1 and use max heap to get the effect of min heap