C++优先级队列中的多次比较？

什么是优先级队列？

优先级队列是类似队列的抽象数据类型，每个元素都有与之关联的某些优先级值。优先级队列中元素的优先级决定了元素被服从的顺序（即它们被取出的顺序）。如果在任何情况下，元素具有相同的优先级，则按照它们在队列中的排序顺序服务。

C++中的priority_queue STL是什么？

“ priority_queue ”是一个容器适配器，它提供了常数时间查找最大元素，代价是对数插入和提取。我们可以使用自定义的比较函数来改变顺序，例如使用 **std :: greater ** 会导致最小的元素显示在队列的顶部。

当我们使用优先级队列时，我们基本上在某些随机访问容器中使用堆，这样做的好处是不会意外地使给定堆无效。

使用自定义比较器的优先级队列

自定义比较器是用于定义将对给定容器进行排序的参数的静态函数。它确定所给容器要排序的方式。

如果我们使用 ‘>’ 符号，则尝试按升序排序，否则将按降序排序，如“ ** > ** ”将在满足 a > b ** （ **a 大于 b ）时返回true，否则将返回false。因此，如果比较器将返回true，则会进行交换，否则不会进行交换。

让我们看一个程序，进一步了解如何应用此概念。

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

// This template is used to print
// the given heap again and again
// irrespective of the given data type
template <class T>
void printQueue(T& q)
{
    while (q.empty() == false) {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
}

// Here we are using a basic priority queue
// and sorting the queue in ascending order
void samplepriorityqueue()
{
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < 10; i++) {
        pq.push(i);
    }
    printQueue(pq);
}

// Here we are using the lambda comparator function
// to sort given priority queue in ascending order
void samplepriorityqueue1()
{
    auto compare = [](int left, int right) {
        return left < right;
    };
    priority_queue<int, vector<int>, decltype(compare)> pq(
        compare);
    for (int i = 0; i < 10; i++) {
        pq.push(i);
    }
    printQueue(pq);
}

// Here we are using a comparator function
// to sort the given priority queue.
// This comparator function can be extended
// to included several other features
struct mycmp {
    bool operator()(int a, int b)
    {
        return a > b;
    }
};

void samplepriorityqueue2()
{
    priority_queue<int, vector<int>, mycmp> pq;
    for (int i = 0; i < 10; i++) {
        pq.push(i);
    }
    printQueue(pq);
}

// Driver code
int main()
{
    samplepriorityqueue();
    samplepriorityqueue1();
    samplepriorityqueue2();
    return 0;
}

输出：

0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9

在这里，我们看到了比较器如何用于比较定义的数据类型，并根据我们给定的比较器对数据进行排序。

C++优先队列中的多重比较

接下来，我们将使用优先队列对用户定义的数据类型进行多重比较，并对已给出的数据进行排序。

我们可以构建一个比较函数，比较多个参数，并根据比较函数中提供的条件对数据结构进行排序。下面是C++优先队列中多个比较的实现。

# include <bits/stdc++.h>
using namespace std;
 
// 用户定义的数据结构的结构
struct jobs {
public:
    int priority;
    int processing;
    int arrivaltime;
    int proccessing_time;
    string job;
    jobs(int priority1, int processing1, int arrivaltime1,
         int proccessing_time1, string s1)
    {
        this->priority = priority1;
        this->processing = processing1;
        this->arrivaltime = arrivaltime1;
        this->proccessing_time = proccessing_time1;
        this->job = s1;
    }
};
 
// 如果优先级相同且我们正在按升序排序，则我们按降序排序。
// 否则，我们按照给定任务的优先级按升序排序
struct compare {
    bool operator()(jobs a, jobs b)
    {
        if (a.priority == b.priority) {
            return a.processing < b.processing;
        }
        return a.priority > b.priority;
    }
};
 
// 驱动程序
int main()
{
    priority_queue<jobs, vector<jobs>, compare> pq;
    for (int i = 0; i < 10; i++) {
        jobs a(rand() % 11, i + 1, rand() % 3 + i,
               rand() % 5 + 3, "something" + to_string(i));
        pq.push(a);
    }
 
    while (pq.empty() == false) {
        jobs b = pq.top();
        pq.pop();
        cout << b.priority << " " << b.processing << " "
             << b.arrivaltime << " " << b.proccessing_time
             << " " << b.job << endl;
    }
    return 0;
}

输出

0 9 10 5 something8
0 8 7 6 something7
3 3 2 4 something2
4 2 3 3 something1
6 1 1 6 something0
7 5 5 3 something4
7 4 5 4 something3
10 10 10 6 something9
10 7 7 5 something6
10 6 5 4 something5