6 priority_queue的介绍和使用
6.1 priority_queue的介绍
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的（默认情况）。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
6.2 priority_queue的使用
优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue 。注意： 默认情况下 priority_queue 是大堆 。
忘记了堆的老铁可以去看看博主讲解的这篇文章：
http://xn--http-u76a//t.csdn.cn/Buh2Q%E2%80%8B
函数声明 |
接口说明 |
priority_queue() priority_queue(first, last) |
构造一个空的优先级队列 |
empty( ) |
检测优先级队列是否为空，是返回true，否则返回false |
top( ) |
返回优先级队列中最大(最小元素)，即堆顶元素 |
push(x) |
在优先级队列中插入元素x |
pop( ) |
删除优先级队列中最大(最小)元素，即堆顶元素 |
我们可以来试试：
priority_queue<int> pq;//仿函数为less,默认建立大堆 pq.push(10); pq.push(1); pq.push(8); pq.push(3); pq.push(15); pq.push(16); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
至于为啥仿函数为less，但是建立的确是大堆这个是大佬们硬性规定的，大家也不要太过于较真。
要实现建立小堆我们调用一下greater仿函数即可。
priority_queue<int,vector<int>,greater<int>> pq;//显示调用仿函数为greater,建立小堆 pq.push(10); pq.push(1); pq.push(8); pq.push(3); pq.push(15); pq.push(16); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
运行结果：
假如我们想比较自定义类型的大小应该咋办？直接用STL自带的仿函数好像并不能够完成，所以我们还得自己再实现一下仿函数。
先把日期类给整出来：
class Date { friend ostream& operator<<(ostream& out, const Date& d);//友元声明 private: int _year; int _month; int _day; public: Date(int year = 1, 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); } }; ostream& operator<<(ostream& out, const Date& d) { out << d._year << "/" << d._month << "/" << d._day << endl; return out; }
大家这时心里可能会想：重载>>还好理解，因为要输出结果嘛，为啥你要重载>和<运算符呀？
不知道大家忘记了没，当我们建堆时有两种调整方式，向上调整和向下调整时都会设计数据的比较，内置类型没事，自定义类型就得我们重载比较运算符了，所以我们要想实现自定义类型的比较，这个是必不可少的。
然后我们就可以实现日期类的比较了：
priority_queue<Date, vector<Date>> pq; pq.push(Date(2023, 2, 7)); pq.push(Date(2021, 2, 9)); pq.push(Date(2023, 2, 8)); pq.push(Date(2024, 2, 6)); while(!pq.empty()) { cout << pq.top() ; pq.pop(); }
运行结果：
但是假如我们push的是日期类的地址，用系统自带的仿函数能够完成吗？
大家想想，由于push的是地址，所以比较的是地址的大小而不是地址指向的内容的大小，所以这种方法肯定是不合理的。
我们可以来试试：
很明显结果是不对的，尽管有时候碰巧结果恰好对的，也只是运气而已。
即我们还得自己写仿函数：
仿函数：
struct p_date_less { bool operator()(Date*& pd1, Date*& pd2) { return *pd1 < *pd2; } }; struct p_date_greater { bool operator()(Date*& pd1, Date*& pd2) { return *pd1 > *pd2; } };
这样就能够正确比较了：
7 priority_queue的模拟实现
template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue { private: Container _con; void adjust_up(size_t child)//假设这里要建立大堆，默认仿函数是less { size_t parent = child - 1 >> 1; while (child > 0) { //if (_con[child] > _con[parent]) Compare cmp;//实例化出一个Cmpare的对象 if (cmp(_con[parent],_con[child]))//由于仿函数中实现的是x<y { swap(_con[child], _con[parent]); child = parent; parent = child - 1 >> 1; } else break; } } void adjust_down(size_t parent) { size_t child = parent * 2 + 1; while (child < _con.size()) { Compare cmp;//实例化出一个Cmpare的对象 if (child + 1 < _con.size() && cmp(_con[child],_con[child+1]))//假如建立大堆，默认仿函数为less,就得满足_con[child]<_con[child+1] child += 1; //if (_con[child] > _con[parent]) if (cmp(_con[parent],_con[child]))//由于仿函数中实现的是x<y { swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else break; } } public: priority_queue() { } template<class InputIterator> priority_queue(InputIterator first, InputIterator last) :_con() { for (int i = _con.size() - 2 >> 1; i >= 0; i--)//向下建堆时间复杂度为O(N) adjust_down(i); } void push(const T& x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { swap(_con[0], _con[size() - 1]); _con.pop_back(); adjust_down(0); } const T& top() { return _con.front(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } };
这个之前在堆那一部分做了较为详细的讲解，这里就不在多说了。
