优先队列

我们知道普通队列的特点是先进先出，但是优先队列的特点则遵守以下两条规则：

- 最大优先队列：无论入队的顺序，当前最大的元素先出列。

- 最小优先队列：无论入队的顺序，当前最小的元素先出列。

说明：在学习优先队列前必须先理解 二叉堆

这时候就是 二叉堆 发挥作用的时候了。我们知道二叉堆有以下特性：

- 最大堆：堆顶是整个数组中最大的元素，且任何父节点的值都大于其子节点

- 最小堆：堆顶是整个数组中最小的元素，且任何父节点的值都小于其子节点

对于优先队列，介绍以下几种 *** 作：

入队 *** 作；

出队 *** 作；

说明：以最小优先队列为例

1.入队 *** 作

优先队列本质上就是用二叉堆来实现的，每次插入一个数据都是插入到数据数组的最后一个位置，然后再做上浮 *** 作，如果插入的数是数组中最大数，自然会上浮到堆顶。如“图1 入队 *** 作”所示：

2.出队 *** 作

出队 *** 作就是返回堆顶最小堆的数据之后用数组最后的数插入到堆顶，之后再做下沉 *** 作。如“图2 出队 *** 作”所示：

因为二叉堆上浮和下沉的时间复杂度都为log2(n)，所以入队和出队的时间复杂度也是log2(n)。

优先队列是基于二叉堆实现的，优先指的是按某种优先级优先出列而不是先入先出。 *** 作系统的阻塞机制正是有优先队列实现。

priority_queue又称为优先队列，其底层是用 堆 来进行实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个。

当然，可以在任何时候往优先队列里面加入（push）元素，而优先队列底层的数据结构堆（heap）会随时调整结构，使得 每次的队首元素都是优先级最大的。

定义：priority_queue<typename>name

和队列不一样的是，优先队列没有front（）和back（）函数，而 只能通过top（）函数来访问队首元素。

（1）push（）

（2）top（）： 可以获得队首元素（即堆顶元素）

（3）pop（）： 队首元素（即堆顶元素）出队

（4）empty（）：和queue一样

（5）size（）：

priority_queue优先级的设置：

下面介绍基本数据类型和结构体类型的优先级设置方法

①基本数据类型的优先级设置

priority_queue<int, vector<int>, less<int>>q        //less<int>表示数字大的优先级越大，而greater<int>表示数字小的优先级越大

priority_queue<int , vector<int >, greater<int>>q   //vector<int>是用来承载底层数据结构堆（heap）的容器

②结构体的优先级设置

完整示例：

此处小于号的重载于排序函数sort中的cmp函数有些类似。事实上，两者的作用确实是类似的， 只不过效果看上去似乎是“相反”的。 在排序中，如果是“return f1.price >f2.price”，那么则是按价格从高到低排序，但是在优先队列中却是把价格低的放到队首。原因在于，优先队列本身默认的规则就是优先级高的放在队首，因此把小于号重载为大于号的功能时只是把这个规则反向了一下。如果读者无法理解，那么不妨记住， 优先队列的这个函数与sort中的cmp函数的效果是相反的。

有没有办法跟sort中的cmp函数那样写在结构体外面呢？

自然是有办法的，只需把friend去掉，把小于号改成一对小括号，再把重载的函数写在结构体外面，同时将其用struct包装起来。

---