How can I create Min stl priority_queue?
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
.
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.
Use std::greater
as the comparison function:
std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;
You can do it in multiple ways:
1. Using greater
as comparison function :
#include <bits/stdc++.h>
using namespace std;
int main()
{
priority_queue<int,vector<int>,greater<int> >pq;
pq.push(1);
pq.push(2);
pq.push(3);
while(!pq.empty())
{
int r = pq.top();
pq.pop();
cout<<r<< " ";
}
return 0;
}
2. Inserting values by changing their sign (using minus (-) for positive number and using plus (+) for negative number :
int main()
{
priority_queue<int>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;
}
3. 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;
}
4. 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; }