Priority Queue for Custom Types

Question

I have the following structure

struct node{ float val; int count; } 

I have several objects of this structure. Now I want to insert these objects into the STL priority queue so that the priority queue orders items in the account. Any idea on how to do this? A preferred minimum heap is preferred. I know how to do this for primitive data types, not structures

Answer 1

Overload <Operator:

 bool operator<(const node& a, const node& b) { return a.count > b.count; } 

I flipped the comparison to get the minimum heap without passing additional arguments to the priority queue. Now you use it as follows:

 priority_queue<node> pq; ... 

Edit: take a look at this post, which seems like an almost exact duplicate: STL Priority Queue in a custom class

Answer 2

 #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; } 

Answer 3

1. Using the comparison function as greater you can use the priority queue as the minimum 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; } 

2. Inserting a value, changing their sign (using minus (-) for a positive number and using plus (+) for a negative number, we can use the priority queue in the reverse 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; } 

3. For custom data types or classes, we need to specify a priority queue for determining how to 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; } 

4. For a custom structure or class, you can use priority_queue in any order. Suppose we want to sort people in descending order by their salary, and if linked, by 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; } 

5. The same result can be obtained with 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 the 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; } 

Answer 4

You need to provide operator< for this structure. Something like:

 bool operator<(node const& x, node const& y) { return x.count < y.count; } 

Now you can use the priority queue from the standard library.

Answer 5

We can define a 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; } 

Answer 6

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);