C++标准模板库（STL）中的优先队列

作为C++中最有用且最具表现力的一种数据结构之一，优先队列在STL中得到了广泛的应用。它能够以O(log n)的时间实现元素的插入和删除，并且可以实现高效的堆排序。在本篇文章中，我们将深入学习STL优先队列的使用方法。

什么是优先队列？

优先队列（Priority Queue）是一种特殊的队列，它可以保证每次取出的元素都是队列中的最大值或最小值。优先队列通常用堆来实现，在C++中，STL提供了相关的函数和类来实现优先队列。

在STL中，优先队列是基于类模板priority_queue<T,Container,Compare>实现的。其中，T表示存储在优先队列中的元素的类型，Container表示作为底层容器的类型，而Compare表示比较器类型。

优先队列的常用函数

STL中优先队列有以下常用的函数：

push()

向优先队列中加入一个元素，这个元素会被自动放到正确的位置上。

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

输出结果：3 2 1

pop()

从优先队列中删除优先级最高的元素。

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

输出结果：3 2 1

top()

获取优先队列中优先级最高的元素的值。

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    cout << "The top element is " << pq.top() << endl;
    return 0;
}

输出结果：The top element is 3

size()

获取优先队列中元素的数量。

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    cout << "The size is " << pq.size() << endl;
    return 0;
}

输出结果：The size is 3

empty()

判断优先队列是否为空。

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> pq;
    if (pq.empty()) {
        cout << "The queue is empty" << endl;
    } else {
        cout << "The queue is not empty" << endl;
    }
    return 0;
}

输出结果：The queue is empty

STL优先队列的比较器

在STL中，比较器是一个可选的模板参数，它用于对元素进行排序。当不提供比较器时，默认使用小于操作符compare作为比较器。如果我们需要自定义比较器，则需要为其指定一个类或者函数，并将其作为priority_queue的第三个参数。

使用默认比较器

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

输出结果：3 2 1

自定义比较器

#include<iostream>
#include <queue>
#include <functional>

using namespace std;

struct MyCompare
{
    bool operator()(const int& a, const int& b) const
    {
        return a > b;
    }
};

int main()
{
    priority_queue<int, vector<int>, MyCompare> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

输出结果：1 2 3

在上面的代码中，我们自定义了MyCompare比较器，并通过第三个参数将其传递给了priority_queue。我们重载了()操作符来实现我们自己的比较逻辑，这里我们采用了一个大根堆的形式。