用户定义类型的优先级队列

Question

我有以下结构

struct node{
   float val;
   int count;

}

我有这个结构的几个对象.现在,我想将这些对象插入到STL的优先级队列中,以便优先级队列按计数对项目进行排序.有关如何这样做的任何想法？优选地,最小堆是优选的.我知道如何对原始数据类型而不是结构进行上述操作

Answer 1

重载<运算符:

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

我已经推翻了比较以实现最小堆,而不会将额外的参数传递给优先级队列.现在你像这样使用它:

priority_queue<node> pq;
...

编辑:看看这篇文章似乎几乎完全重复:自定义类的STL优先级队列

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. 使用greater作为比较函数，您可以使用优先级队列作为最小堆，

   #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. 通过更改符号来插入值（使用减号 (-) 表示正数，使用加号 (+) 表示负数，我们可以以相反的顺序使用优先级队列。

   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. 对于自定义数据类型或类，我们需要一个告诉优先级队列的方式来了解它将对我们的数据进行排序的顺序。

   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. 对于自定义结构或类，您可以priority_queue按任何顺序使用。假设，我们想根据工资降序对人进行排序，如果并列则根据他们的年龄排序。

   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. 通过运算符重载可以获得相同的结果：

   struct people
   {
       int age,salary;
   
       bool operator< (const people & p) const
       {
           if(salary==p.salary)
           {
               return age>p.age;
           } else {
               return salary>p.salary;
           }
       }
   };
   

在主函数中：

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