C++优先队列的使用

1. 什么是priority_queue

priority_queue是C++中的容器，实现优先队列。由于底层采用堆实现，所以插入和删除操作的时间复杂度为O(logn)，查找队首元素的时间复杂度为O(1)。

2. 构造priority_queue

【1】使用priority_queue需要先包含头文件。以下是priority_queue的基本语法：

#include 
priority_queue<int> pq;

默认情况下，priority_queue是一个大顶堆，即队首元素是最大的元素，由大到小排序。
 

【2】如果是自定义比较，比如比较从小到大比较或不坏类中的某个元素，则在声明priority_queue对象时，需要指定元素类型和比较函数。

具体语法：

// 声明一个元素类型为T，比较函数为Compare的priority_queue对象
priority_queue, Compare> pq;

其中，T为元素类型，std::vector为底层容器类型，Compare为元素的比较函数，是函数对象。

例如若要声明一个整型优先队列，要求从小到大排序，可以这样写：

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

例如若要声明一个字符串优先队列，要求按照字符串大小从小到大排序，可以这样写：

// 自定义比较函数
struct cmp {
    bool operator() (const std::string& s1, const std::string& s2) {
        return s1.size() > s2.size();  // 按字符串长度从小到大排序
    }
};
 
priority_queue, cmp> pq;

【3】用已有的优先队列赋值

priority_queue<int> pq(vec.begin(), vec.end()); // 创建一个包含vec中所有元素的优先队列

3. priority_queue的常用操作

3.1 插入元素

使用成员函数push()可以向priority_queue中插入一个元素，插入后会自动按照优先级调整元素位置。

pq.push(10); // 向队列中插入元素10 pq.push(20); // 向队列中插入元素20

3.2 访问队首元素

使用成员函数top()可以访问priority_queue中的队首元素，即最大（小）值。

int max_element = pq.top(); // 获取大顶堆的队首元素，即最大值

3.3 删除队首元素

使用成员函数pop()可以删除priority_queue中的队首元素，即最大（小）值。

pq.pop(); // 删除大顶堆的队首元素，即最大值

3.4 检查队列是否为空

使用成员函数empty()可以检查priority_queue是否为空。

if (pq.empty()) { 
    // 队列为空 
}

3.5 获取队列大小

使用成员函数size()可以获取priority_queue中元素的个数。

int count = pq.size(); // 获取队列中元素的个数