深入了解C++优先队列(priority_queue)的使用方法

什么是优先队列？

优先队列(Priority Queue)是一种数据结构，其本质是一个队列，但是队列中的元素都被赋予了优先级。优先级最高的元素最先被取出。

C++的优先队列(priority_queue)的用法

在C++中，优先队列(priority_queue)类定义在头文件中，其基本用法如下：

#include <queue>

std::priority_queue<T> pq; // 定义一个优先队列

其中，T代表队列中元素的类型。优先队列默认按照less从大到小排序，即优先级最高的元素为最大的元素。如果需要按照从小到大排序，则需要定义greater。

std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 按照从小到大排序

push和pop

向优先队列中添加元素可通过push函数实现：

pq.push(10); 
pq.push(20); 
pq.push(30); 

从优先队列中取出元素可通过pop函数实现：

pq.pop(); // 取出最大的元素

top和empty

查看优先队列中最高优先级的元素可通过top函数实现：

std::cout << pq.top(); // 输出最大的元素

判断优先队列是否为空可通过empty函数实现：

if (pq.empty()) {
    std::cout << "优先队列为空";
}

示例1：使用优先队列来维护一个最大值队列

给定一个整型序列，我们需要动态维护其中的最大值。可以使用优先队列来实现：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    priority_queue<int> q; // 定义一个优先队列

    for (int i = 0; i < v.size(); i++) {
        q.push(v[i]); // 将元素加入队列中
        cout << q.top() << " "; // 输出队列中的最大值
    }

    return 0;
}

输出结果为：

3 3 4 4 5 5 5 6 6 6 6

示例2：使用优先队列来实现堆排序

在堆排序中，利用最大堆或最小堆实现排序。使用优先队列来实现最大堆或最小堆，从而达到排序的效果：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    priority_queue<int> q; // 定义一个最大堆

    for (int i = 0; i < v.size(); i++) {
        q.push(v[i]); // 将元素加入最大堆中
    }

    while (!q.empty()) {
        cout << q.top() << " "; // 从最大堆中取出元素
        q.pop();
    }

    return 0;
}

输出结果为：

9 6 5 5 5 4 3 3 2 1 1