I have the below struct:
struct node { float val; int count; } I have several objects of this struct. Now, I want to insert these objects into a priority queue of STL such that the priority queue orders the items by count. Any idea on how to do so? Preferably a min-heap is preferred. I know how to do the above for primitive data types, not structs
Overload the < operator:
bool operator<(const node& a, const node& b) { return a.count > b.count; } I have reversed the comparison to achieve min heap without passing extra arguments to the priority queue. Now you use it like this:
priority_queue<node> pq; ... Edit: take a look at this post which seems to be almost exact duplicate: STL Priority Queue on custom class
template<class T> priority_queue). Internally it uses the < operator for comparison of the elements pushed in it. So if you have not defined this operator for the class you are pushing in a priority_queue you will get an compilation error. For the question about pointers take a look at the edit of my comment.
return a.count < b.count;?I have reversed the comparison to achieve min heap wihtout passing extra arguments to the priority queue.
Define overloaded operators only if their meaning is obvious, unsurprising, and consistent with the corresponding built-in operators. - from Google C++ style guide.#include <iostream> #include <queue> #include <vector> using namespace std; class Boxer{ public: string name; int strength; }; struct Comp{ bool operator()(const Boxer& a, const Boxer& b){ return a.strength<b.strength; } }; int main(){ Boxer boxer[3]; boxer[0].name="uday", boxer[0].strength=23; boxer[1].name="manoj", boxer[1].strength=33; boxer[2].name="rajiv", boxer[2].strength=53; priority_queue< Boxer, vector<Boxer>, Comp> pq; pq.push(boxer[0]); pq.push(boxer[1]); pq.push(boxer[2]); Boxer b = pq.top(); cout<<b.name; //result is Rajiv return 0; } 
Using greater as comparison function you can use priority queue as min heap,
#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; } Inserting value by changing their sign (using minus (-) for positive number and using plus (+) for negative number we can use priority queue in reversed order.
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; } For custom data types or classes we need a to tell priority queue a way of knowing on which order it will sort our data.
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; } For 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; } You need to provide operator< for that struct. Something like:
bool operator<(node const& x, node const& y) { return x.count < y.count; } Now you can use a priority queue from the standard library.
Since C++11, you can write
auto comparer = [](const auto& a, const auto& b) { return a.priority < b.priority; }; std::priority_queue<Item, std::vector<Item>, decltype(comparer)> queue(comparer); We can define user defined comparator class:
#include<bits/stdc++.h> using namespace std; struct man { string name; int priority; }; class comparator { public: bool operator()(const man& a, const man& b) { return a.priority<b.priority; } }; int main() { man arr[5]; priority_queue<man, vector<man>, comparator> pq; for(int i=0; i<3; i++) { cin>>arr[i].name>>arr[i].priority; pq.push(arr[i]); } while (!pq.empty()) { cout<<pq.top().name<<" "<<pq.top().priority; pq.pop(); cout<<endl; } return 0; } 
#include <iostream> #include <bits/stdc++.h> using namespace std; class Person { public: string name; int age; Person(string str,int num) { name = str; age = num; } }; // FUNCTOR class compare { public: bool operator()(Person a,Person b) { cout << "Comparing " << a.age << " with " << b.age << endl; return a.age < b.age; } }; int main() { int n; cin >> n; priority_queue <Person, vector<Person> , compare> pq; for(int i=1;i<=n;i++) { string name; int x; cin >> name; cin >> x; Person p(name,x); pq.push(p); } int k = 3; for(int i=0;i<k;i++) { Person p = pq.top(); pq.pop(); cout << p.name << " " << p.age << endl; } return 0; }Operator() is also commonly overloaded to implement functors or function object. For example we have a structure Person which have some default ways of searching and sorting a person by age but we want our customized ways with some other parameter like weight so we may use our own custom functor. Priority queue is one such container which accepts a functor so it knows how to sort the objects of custom data types. Each time a comparison has to be done, a object is instantiated of class compare, and it is passed two objects of person class for comparison.
