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

Question

我有以下结构体：

struct node {
   float val;
   int count;
}

我有几个这个结构的对象。现在，我想将这些对象插入STL的优先队列中，以使优先队列根据计数来排序这些项。 有任何方法吗？最好是使用小根堆。我知道如何对原始数据类型执行上述操作，但不知道如何对结构体进行操作。

- Programmer

Answer 1

重载 < 运算符：

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

我已经反转了比较操作，以实现最小堆而无需将额外参数传递给优先队列。 现在你可以这样使用：

priority_queue<node> pq;
...

编辑：看一下这篇帖子，它似乎是几乎完全相同的重复：STL Priority Queue on custom class

- Ivaylo Strandjev

---

如果我在队列中推送指针，会发生什么情况？也就是说，节点是指针类型。这会改变什么吗？你能解释一下为什么必须重写 < 运算符以及它的工作原理吗？ - Programmer

优先队列是一个模板类（假设它的模板为template<class T> priority_queue）。它内部使用 < 运算符来比较插入其中的元素。如果你没有为插入优先队列中的类定义这个运算符，你将会得到一个编译错误。关于指针的问题，请查看我的评论编辑。 - Ivaylo Strandjev

应该不是return a.count < b.count;吗？ - 425nesp

我已经修改了比较方式，实现了最小堆而无需向优先队列传递额外参数。 - Ivaylo Strandjev

@IvayloStrandjev 操作符不应以这种相反的方式进行重载。仅在其含义明确、不令人惊讶且与相应的内置操作符一致的情况下定义重载操作符。- 来自Google C++风格指南。 - Dejan

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

- Uday Hiwarale

---

谢谢分享。这真的很有用，可以让人得到完整的图片。 - aLearner

为什么要传递vector<Boxer>？为什么要传递结构体而不是函数？为什么要重载()运算符而不是<? @mohit，如果一个显然是C++新手的人提出问题，如果没有解释，我不会称其为好答案。 - Oğuz Yıldız

嗨！我不明白为什么我们需要提供第二个参数 "vector<Boxer>"，我的意思是，即使没有这个参数，它也能工作，对吗？ - aroma

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

通过改变数值的符号（使用减号（-）表示正数，使用加号（+）表示负数），我们可以按照相反的顺序使用优先队列。

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

对于自定义数据类型或类，我们需要告诉优先队列如何知道按照哪个顺序对我们的数据进行排序。

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

对于自定义的结构体或类，您可以使用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;
    }

通过运算符重载也可以得到相同的结果：

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

- Taohidul Islam

Answer 4

你需要为该结构体提供operator<。像这样：

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

现在您可以使用标准库中提供的优先队列。

- R. Martinho Fernandes

Answer 5

自C++11以来，您可以编写：

auto comparer = [](const auto& a, const auto& b) {
    return a.priority < b.priority;
};
std::priority_queue<Item, std::vector<Item>, decltype(comparer)> queue(comparer);

- yukinarit

Answer 6

我们可以定义用户自定义比较器类：

代码片段：

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

- rashedcs

Answer 7

#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() 也常常被重载来实现函数对象或者函数符。例如，我们有一个名为 Person 的结构体，它有一些默认的按年龄搜索和排序人员的方式，但是我们想要使用一些其他参数（如体重）来自定义我们的方式，因此我们可以使用自己的自定义函数符。优先队列就是这样一个容器，它接受一个函数符，以便知道如何对自定义数据类型的对象进行排序。每次需要进行比较时，都会实例化一个 compare 类的对象，并将两个 person 类的对象传递给它进行比较。

- Amrit Kanoi