标签：优先队列

C++优先队列是一种特殊的容器，它能够以任意顺序存储元素，并且能够快速找到队列中的最大(或最小)元素，优先队列中的元素按照一定的顺序排列，这个顺序可以是元素的值、元素的键或者元素的索引等，在C++标准库中，优先队列主要由 priority_queue容器适配器实现。,1、基本数据结构,,优先队列底层使用了一个最大堆(MaxHeap)来实现，最大堆是一种特殊的二叉树，它的每个节点的值都大于或等于其子节点的值，在最大堆中，根节点总是最大的，而每个叶子节点都是最小的，这样，我们可以通过访问根节点(即最大值)来快速找到队列中的最大元素。,2、插入和删除操作,优先队列支持在队尾插入元素和删除队头元素的操作，插入操作的时间复杂度为O(logN),删除操作的时间复杂度也为O(logN)，这是因为最大堆的性质决定了插入和删除操作的时间复杂度。,3、查找最大元素,在优先队列中，最大元素就是根节点，查找最大元素的操作非常简单，只需要访问根节点即可。,,1、引入头文件,要使用C++优先队列，首先需要引入头文件 <queue>,它包含了 priority_queue容器适配器所需的类模板定义。,2、创建优先队列,创建优先队列时，需要指定元素类型以及比较函数或者lambda表达式，比较函数用于确定元素之间的顺序关系，如果没有提供比较函数，则默认使用元素的值进行比较。,3、向优先队列中插入元素,,使用 push()方法向优先队列中插入元素，如果没有指定比较函数或者lambda表达式，那么默认使用元素的值进行比较。,4、从优先队列中删除并返回最大元素,使用 top()方法获取优先队列中的最大元素，然后使用 pop()方法将其删除，如果没有指定比较函数或者lambda表达式，那么默认使用元素的值进行比较。