priority_queue的介绍
1.解释以上内容
priority_queue（优先级队列）跟stack、queue一样，都是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大或者最小的（默认最大）。
2.优先队列的底层数据结构是用堆来实现的。
3.作为容器适配器，priority_queue默认是由 vector类
来实现的。优先队列（堆）这种数据结构需要快速随机访问元素的能力。除了vector，deque类也可以用来作为优先队列的底层容器。严格来说，只要满足以下能力的容器都可以作为优先队列的底层容器：
(1)empty()：检测容器是否为空
(2)size()：返回容器中有效元素个数
(3)front()：返回容器中第一个元素的引用
(4)push_back()：在容器尾部插入元素
(5)pop_back()：删除容器尾部元素
库中priority_queue的使用
虽然我们将priority_queue称为优先队列，但是其本质就是堆，而堆的本质又是一颗完全二叉树。所以，我们需要一种符合以上这些数据结构所有特点的容器来存储元素。vector就显得非常合适。可以用下标映射节点的父子关系，高效尾删，快速随机访问。
现在我们来看库中priority_queue主要有哪些功能吧
| 函数声明 | 接口说明 |
| priority_queue()和priority_queue(first, last) | 构造一个空的优先队列 |
| pop() | 弹出堆顶元素，即优先队列的最大值或者最小值 |
1.使用演示：创建大堆，默认就是最大堆
2.使用演示：创建最小堆， 将第三个模板参数换成greater比较方式
其中，greater是一个类模板，实例化出来之后可以当函数一样使用（仿函数）。greater里面控制了比较对象的关系，是一个比较剂。
什么叫仿函数？
仿函数又叫函数对象。本质是一个类实例化出来的对象，因为重载了()我们可以像使用函数一样使用其operator()。
比如下面就是一个仿函数：
class fun { public: int operator()(int& A, int& B) { return A + B; } };
我们可以创建一个fun类来调用operator():
class fun { public: int operator()(int& A, int& B) { return A + B; } }; void test3() { fun f; int a = 1; int b = 2; cout << f(a, b) << endl; }
借用模板之后，仿函数比普通函数显得更加灵活。
priority_queue<int, vector<int>, greater<int>>中的greater其实就是一个函数对象，通过实例化int类型，来控制两个int类型变量的顺序关系。
模拟实现greater类：
template<class T> class Greater { public: bool operator()(T& A, T& B) { return A > B; } };
当我们将greater作为第三个参数传递给priority_queue时，二叉树的父子节点的关系也就确定了，即确定了优先级。
那为什么默认是小堆呢？
这是因为priority_queue的第三个参数的缺省值设置成了less,而less其实就是一个仿函数，控制了堆顶元素永远是最小值。
当然，我们同样可以不用仿函数做参数，用一个函数指针也可以达到一样的效果。
值得注意的是，如果priority_queue的元素是自定义类型，那我们需要在自定义类型中提供比较运算符的重载，以便达到我们想要的目的。
给出以下代码示例：
class Date { public: Date(int year = 1900, int month = 1, int day = 1) : _year(year) , _month(month) , _day(day) {} bool operator<(const Date& d)const { return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day); } bool operator>(const Date& d)const { return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day); } friend ostream& operator<<(ostream& _cout, const Date& d) { _cout << d._year << "-" << d._month << "-" << d._day; return _cout; } private: int _year; int _month; int _day; }; void TestPriorityQueue() { // 大堆，需要用户在自定义类型中提供<的重载 priority_queue<Date> q1; q1.push(Date(2018, 10, 29)); q1.push(Date(2018, 10, 28)); q1.push(Date(2018, 10, 30)); cout << q1.top() << endl; // 如果要创建小堆，需要用户提供>的重载 priority_queue<Date, vector<Date>, greater<Date>> q2; q2.push(Date(2018, 10, 29)); q2.push(Date(2018, 10, 28)); q2.push(Date(2018, 10, 30)); cout << q2.top() << endl; }
模拟实现prioprity_queue类
#define _CRT_SECURE_NO_WARNINGS 1 #include<vector> #include<algorithm> template<class T> class Less { public: bool operator()(T& A, T& B) { return A < B; } }; template<class T> class Greater { public: bool operator()(T& A, T& B) { return A > B; } }; template<class T,class Container=std::vector<T>, class Compare = Less<T> > class priority_queue { public: int size() { return _con.size(); } bool empty() { return _con.empty(); } void adjust_up(int n) { int child = n; int father = (n - 1) / 2; Compare com; while (child >= 0) { if (com(_con[father], _con[child])) { std::swap(_con[father], _con[child]); child = father; father = (child - 1) / 2; } else { break; } } } void adjust_down(int n) { int father = n; int child = father * 2 + 1; Compare com; while (child < size()) { if (child + 1 < size() && com(_con[child ],_con[child+1])) { child++; } if (com(_con[father], _con[child])) { std::swap(_con[father], _con[child]); father = child; child = child * 2 + 1; } else { break; } } } void push(const T& val) { _con.push_back(val); adjust_up(_con.size()-1); } T& top() { return _con[0]; } void pop() { std::swap(_con[0], _con[size() - 1]); _con.pop_back(); adjust_down(0); } T& operator[](size_t n) { return _con[n]; } private: Container _con; };
