优先队列概述
队列是一种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;
网友评论