c++ - ユーザー定義型の優先キュー

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

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

Answer 3

その構造体を提供する必要がありますoperator<。何かのようなもの：

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

標準ライブラリのプライオリティ キューを使用できるようになりました。

Answer 4

ユーザー定義のコンパレータ クラスを定義できます。

コードスニペット ：

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