c++优先队列怎么使用

C++优先队列是一种特殊的容器，它能够以任意顺序存储元素，并且能够快速找到队列中的最大(或最小)元素，优先队列中的元素按照一定的顺序排列，这个顺序可以是元素的值、元素的键或者元素的索引等，在C++标准库中，优先队列主要由priority_queue容器适配器实现。

优先队列的基本概念

1、基本数据结构

优先队列底层使用了一个最大堆(MaxHeap)来实现，最大堆是一种特殊的二叉树，它的每个节点的值都大于或等于其子节点的值，在最大堆中，根节点总是最大的，而每个叶子节点都是最小的，这样，我们可以通过访问根节点(即最大值)来快速找到队列中的最大元素。

2、插入和删除操作

优先队列支持在队尾插入元素和删除队头元素的操作，插入操作的时间复杂度为O(logN),删除操作的时间复杂度也为O(logN)，这是因为最大堆的性质决定了插入和删除操作的时间复杂度。

3、查找最大元素

在优先队列中，最大元素就是根节点，查找最大元素的操作非常简单，只需要访问根节点即可。

C++优先队列的使用

1、引入头文件

要使用C++优先队列，首先需要引入头文件<queue>,它包含了priority_queue容器适配器所需的类模板定义。

include <queue>

2、创建优先队列

创建优先队列时，需要指定元素类型以及比较函数或者lambda表达式，比较函数用于确定元素之间的顺序关系，如果没有提供比较函数，则默认使用元素的值进行比较。

std::priority_queue<int> pq; // 创建一个整型优先队列
std::priority_queue<int, std::vector<int>, std::greater<int>> pq2; // 创建一个整型优先队列，按照降序排列
std::priority_queue<int, std::vector<int>, [](int a, int b){return a > b;}> pq3; // 创建一个整型优先队列，按照自定义的比较函数进行排序

3、向优先队列中插入元素

使用push()方法向优先队列中插入元素，如果没有指定比较函数或者lambda表达式，那么默认使用元素的值进行比较。

pq.push(3); // 向优先队列中插入一个整数3
pq2.push(3); // 向优先队列中插入一个整数3,结果是降序排列的
pq3.push(3); // 向优先队列中插入一个整数3,结果是升序排列的(假设自定义的比较函数始终返回false)

4、从优先队列中删除并返回最大元素

使用top()方法获取优先队列中的最大元素，然后使用pop()方法将其删除，如果没有指定比较函数或者lambda表达式，那么默认使用元素的值进行比较。

int max1 = pq.top(); // 获取优先队列中的最大元素并赋值给max1变量
int max2 = pq2.top(); // 获取优先队列中的最大元素并赋值给max2变量(降序排列)
int max3 = pq3.top(); // 获取优先队列中的最大元素并赋值给max3变量(升序排列)(假设自定义的比较函数始终返回false)
pq.pop(); // 删除并返回最大元素(默认升序排列)
pq2.pop(); // 删除并返回最大元素(降序排列)