Как использовать приоритетную очередь STL для объектов?

вы бы написали класс компаратора, например:

struct CompareAge {
    bool operator()(Person const & p1, Person const & p2) {
        // return "true" if "p1" is ordered before "p2", for example:
        return p1.age < p2.age;
    }
};

и использовать это в качестве аргумента компаратора:

priority_queue<Person, vector<Person>, CompareAge>

используя greater дает противоположный порядок по умолчанию less, что означает, что очередь даст вам самое низкое значение, а не самое высокое.

очередь приоритетов-это абстрактный тип данных, который захватывает идею контейнера, элементы которого имеют" приоритеты", прикрепленные к ним. Элемент с наивысшим приоритетом всегда появляется в начале очереди. Если этот элемент удален, то следующий элемент с наивысшим приоритетом выдвигается вперед.

стандартная библиотека C++ определяет шаблон класса priority_queue со следующими операциями:

push: вставить элемент в prioity очередь.

top: возвращает (не удаляя его) элемент с наивысшим приоритетом из очереди приоритетов.

поп: удаление элемента с наивысшим приоритетом из очереди приоритетов.

в размере: возвращает количество элементов в очереди.

пустой: возвращает true или false в зависимости от того, приоритетная очередь пуста или нет.

следующий фрагмент кода показывает, как построить две очереди приоритетов, одна из которых может содержать целые числа, а другая-символьные строки:

#include <queue>

priority_queue<int> q1;
priority_queue<string> q2;

ниже приведен пример использования приоритетной очереди:

#include <string>
#include <queue>
#include <iostream>

using namespace std;  // This is to make available the names of things defined in the standard library.

int main()
{
    piority_queue<string> pq; // Creates a priority queue pq to store strings, and initializes the queue to be empty.

    pq.push("the quick");
    pq.push("fox");
    pq.push("jumped over");
    pq.push("the lazy dog");

    // The strings are ordered inside the priority queue in lexicographic (dictionary) order:
    // "fox", "jumped over", "the lazy dog", "the quick"
    //  The lowest priority string is "fox", and the highest priority string is "the quick"

    while (!pq.empty()) {
       cout << pq.top() << endl;  // Print highest priority string
       pq.pop();                    // Remmove highest priority string
    }

    return 0;
}

вывод этой программы:

the quick
the lazy dog
jumped over
fox

поскольку очередь следует за приоритетной дисциплиной, строки печатаются от самого высокого до самого низкого приоритета.

иногда нужно создать очередь приоритетов, чтобы содержать пользовательские объекты. В этом случае приоритетная очередь должна знать критерий сравнения, используемый для определения того, какие объекты имеют наивысший приоритет. Это делается с помощью объекта функции beloging к классу, который перегружает оператор (). Перегруженный () действует как

struct Time {
    int h; 
    int m; 
    int s;
};

class CompareTime {
    public:
    bool operator()(Time& t1, Time& t2) // Returns true if t1 is earlier than t2
    {
       if (t1.h < t2.h) return true;
       if (t1.h == t2.h && t1.m < t2.m) return true;
       if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
       return false;
    }
}

приоритетной очереди в магазин раз в соответствии с выше критерий сравнения определялся бы следующим образом:

priority_queue<Time, vector<Time>, CompareTime> pq;

Here is a complete program:

#include <iostream>
#include <queue>
#include <iomanip>

using namespace std;

struct Time {
    int h; // >= 0
    int m; // 0-59
    int s; // 0-59
};

class CompareTime {
public:
    bool operator()(Time& t1, Time& t2)
    {
       if (t1.h < t2.h) return true;
       if (t1.h == t2.h && t1.m < t2.m) return true;
       if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
       return false;
    }
};

int main()
{
    priority_queue<Time, vector<Time>, CompareTime> pq;

    // Array of 4 time objects:

    Time t[4] = { {3, 2, 40}, {3, 2, 26}, {5, 16, 13}, {5, 14, 20}};

    for (int i = 0; i < 4; ++i)
       pq.push(t[i]);

    while (! pq.empty()) {
       Time t2 = pq.top();
       cout << setw(3) << t2.h << " " << setw(3) << t2.m << " " <<
       setw(3) << t2.s << endl;
       pq.pop();
    }

    return 0;
}

программа печатает время от последнего до самого раннего:

5  16  13
5  14  20
3   2  40
3   2  26

если бы мы хотели, чтобы самые ранние времена имели самый высокий приоритет, мы бы переопределили CompareTime следующим образом:

class CompareTime {
public:
    bool operator()(Time& t1, Time& t2) // t2 has highest prio than t1 if t2 is earlier than t1
    {
       if (t2.h < t1.h) return true;
       if (t2.h == t1.h && t2.m < t1.m) return true;
       if (t2.h == t1.h && t2.m == t1.m && t2.s < t1.s) return true;
       return false;
    }
};

этот фрагмент кода может помочь..

#include <bits/stdc++.h>
using namespace std;    

class node{
public:
    int age;
    string name;
    node(int a, string b){
        age = a;
        name = b;
    }
};

bool operator<(const node& a, const node& b) {

    node temp1=a,temp2=b;
    if(a.age != b.age)
        return a.age > b.age;
    else{
        return temp1.name.append(temp2.name) > temp2.name.append(temp1.name);
    }
}

int main(){
    priority_queue<node> pq;
    node b(23,"prashantandsoon..");
    node a(22,"prashant");
    node c(22,"prashantonly");
    pq.push(b);
    pq.push(a);
    pq.push(c);

    int size = pq.size();
    for (int i = 0; i < size; ++i)
    {
        cout<<pq.top().age<<" "<<pq.top().name<<"\n";
        pq.pop();
    }
}

выход:

22 prashantonly
22 prashant
23 prashantandsoon..

мы можем определить пользовательский компаратор: .Приведенный ниже код может быть полезен для вас.

Фрагмент Кода :

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

вход :

Бэтмэн 2
ГОКУ 9
Марио 4

выход

ГОКУ 9
Марио 4
Бэтмен 2