c++优先队列用法详解

1. 优先队列的概念

优先队列是一种抽象数据结构，在队列基础上，每个元素拥有一个优先级，元素按优先级高低排序。具有高优先级的元素先被处理。优先队列可以用数组、链表和堆等数据结构来实现。

在c++中，优先队列是由头文件 <queue> 定义的，是一个模板类，可以存储任何数据类型。默认情况下，优先队列使用 std::less 作为其排序准则，即按照从小到大的顺序排序。优先队列支持以下操作：

push()

pop()

top()

2. 优先队列的用法

2.1 push()

当我们向优先队列中添加元素时，调用 push() 函数即可。下面是一个例子：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

以上代码会输出：30 20 10。我们可以看到，元素被按照从大到小的顺序插入到了队列中。注意，这里的 priority_queue 是默认情况下使用 std::less 作为排序准则的，即按照从小到大的顺序排序。如果我们想按照从大到小的顺序排序，可以使用 std::greater 作为排序准则：

priority_queue<int, vector<int>, greater<int>> pq;

2.2 pop()

当我们需要从优先队列中删除元素时，调用 pop() 函数即可。以下是一个例子：

priority_queue<int, vector<int>, greater<int>> pq;
pq.push(10);
pq.push(30);
pq.push(20);
pq.pop();
while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
}

以上代码会输出：20 30，我们可以看到，在我们删除了元素 10 之后，优先队列中只剩下了元素 20 和 30。

2.3 top()

当我们需要获取优先队列中具有最高优先级的元素时，调用 top() 函数即可。以下是一个例子：

priority_queue<int, vector<int>, greater<int>> pq;
pq.push(10);
pq.push(30);
pq.push(20);
cout << pq.top() << endl;

以上代码会输出：10，我们可以看到，我们成功地获取了具有最高优先级的元素。

3. 小结

优先队列是一种抽象数据结构，可以用于存储具有优先级的元素，这些元素按照优先级高低排序。c++中的优先队列是由头文件 <queue> 定义的模板类，可以存储任何数据类型。默认情况下，优先队列使用 std::less 作为排序准则，但是我们可以使用 std::greater 作为排序准则。优先队列支持三个操作：push()、pop() 和 top()。