Priority queue for user-defined types
-
26-04-2021 - |
Domanda
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
Soluzione
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 wihtout 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
Altri suggerimenti
#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.
We can define user defined comparator class:
Code Snippet :
#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;
}
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);