C++ 优先队列的用法

优先队列概述

队列是一种FIFO(先进先出) 的数据模型

队列基本模型

通常的协议包含基本的操作

• push 压入队列，在队尾进入队列
• pop 弹出队头的元素

如果队列两头都可以进出元素，就成为一个双端队列

普通的队列元素没有特意组织过，有一种应用，比如图算法中经常用到，这种应用需要在队列中选出最大或最小的元素，那么普通的队列就无法做到这点。
当然可以遍历队列，找出最大值，这样的计算效率大约是 O(n) 的复杂度，在大型的队列中，这将会形成一个负担，于是人们发明了一种数据结构，它可以保证根部的元素是最大的(或是最小的)取决于需要。

这就是所谓的优先队列。
最大堆是一种二叉树结构，它的根部元素不小于所有的子节点元素，同时它的左右子树也满足这个性质

一个最大堆的例子

如果弹出根部的 56 这个元素，二叉堆的结构将会遭到，破坏，需要进行一种叫做 “上滤” 的操作，右边更大的 39 会提到根部作为顶部元素，同时 39 的两个左右节点将会选出一个较大的元素 23，来填充39原来的位置，递归向下直到底部，下面是 56 被弹出之后，重新调整后的二叉堆，灰色部分代表发生变换的元素

删去根部元素后调整的结构

经过研究和理论佐证，二叉堆的插入和删除可以在 的时间复杂度内完成，这个时间界是比 好的多的界，几乎在大多数应用场景下可以看成是常数时间界的性能。

因此二叉堆很适合作为优先队列的内部实现。

• push 压入队列的元素将会和原有的数据进行调整，保证仍然是一个最大堆/最小堆结构
• pop 每次弹出的元素是最大值，弹出之后剩下的元素需要调整，保证仍然是一个最大堆/最小堆结构

C++ 的优先队列

标准库提供了一个 priority_queue 类。
的声明为

template <class _Tp, class _Container = vector<_Tp>,
          class _Compare = less<typename _Container::value_type> >
class _LIBCPP_TEMPLATE_VIS priority_queue

定义优先队列的方式

std::priority_queue<int> q; //默认是最大堆
std::priority_queue<int, vector<int>, less<int> > q2; //最小堆

std::priority_queu<pair<int, int> > // 点对元素的队列

对于比较的法则，一般是采用默认最大堆的方式，但有时候我们往队列中放置自定义的类型就需要自定义比较函数

仿函数方法，个人推荐，因为，这个比较的类和类型没有强绑定，我们随时可以重写仿函数内的规则

struct myCompare {
            bool operator() (std::pair<int, double> a, std::pair<int, double> b) {
                
                return a.second < b.second;
            }
        };

std::priority_queue<pair<int, double>, vector<pair<int, double>>, myCompare > q;