个人主页 ： zxctscl
如有转载请先通知
文章目录
1. priority_queue的介绍2. priority_queue的使用3. 函数模板与类模板4. 仿函数5. priority_queue模拟实现5.1 push5.2 pop5.3 empty5.4 size5.5 top5.6 仿函数实现大小堆5.7 实现自定义类型的优先级队列 6. 附模拟实现代码
1. priority_queue的介绍
代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
2. priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
来代码测试看看大堆：
void test_priority_queue(){priority_queue<int> pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}int main(){test_priority_queue();return 0;}默认情况下，priority_queue是大堆
priority_queue默认情况下是less大堆，
想要priority_queue默认改为小堆，就得传三个参数。
用代码来测试一下:
#include<iostream>using namespace std;#include<vector>#include<queue>void test_priority_queue(){priority_queue<int,vector<int>,greater<int>> pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}int main(){test_priority_queue();return 0;}
3. 函数模板与类模板
sort默认排序也是升序
vector<int> v = { 3,1,7,4,6,3 };// 升序sort(v.begin(), v.end());for (auto e : v){cout << e << " ";}cout << endl;
想要将sort排序默认改为降序，就得加仿函数：
vector<int> v = { 3,1,7,4,6,3 };sort(v.begin(), v.end(), greater<int>());for (auto e : v){cout << e << " ";}cout << endl;
sort这里是函数模板，函数参数传的是对象。
而priority_queue传的是类型，需要显示实例化
4. 仿函数
仿函数就是一个函数对象，就是一个类型。
先来实现一个类：
struct Less{bool operator()(const int& x, const int& y){return x < y;}};int main(){Less lessfunc;cout << lessfunc(1, 2) << endl;cout << lessfunc.operator()(1, 2) << endl;cout << Less()(1, 2) << endl;return 0;}如果单独看红色框这一行，就会以为lessfunc是一个函数名，但它并不是，它是一个像函数的对象。
仿函数它的对象可以像函数一样去使用，本质上就是调用operator():
这两个是等价的：
还有能用匿名对象：
它本质上就是：
这里重载函数调用参数的()，其实就像[]一样，v[0]也就是v.operator：
本质上就是参数留下，变成运算符的操作数。
运算符重载中operator加运算符才是函数名，省略掉的就是.operator加括号。
一个类只要重载了operator()就可以调仿函数。
加模板就直接可以重载为泛型，什么类型就可以支持。
template<class T>struct Less{bool operator()(const T& x, const T& y){return x < y;}};int main(){Less<int> lessfunc;cout << lessfunc(1, 2) << endl;cout << lessfunc.operator()(1, 2) << endl;cout << Less<int>()(1, 2) << endl;cout << Less<int>().operator()(1, 2) << endl;return 0;}这里定义类用struct和class有什么区别？
一般所有数据都公有就用struct，
有些公有，有些私有就用class。
5. priority_queue模拟实现
直接复用容器
5.1 push
插入一个数据后，向上调整，具体实现过程有需要可以看【数据结构】堆的实现
push代码：
void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child>0){if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}
5.2 pop
就这样删除效率太低了，通常首位交换一下。向下调整，具体实现过程有需要可以看【数据结构】堆的实现
pop代码实现：
void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child< _con.size()){if (child + 1<_con.size() && _con[child + 1]>_con[child]){++child;}if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);parent=child ;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}5.3 empty
bool empty(){return _con.empty();}5.4 size
size_t size(){return _con.size();}5.5 top
const T& top(){return _con.back[0];}5.6 仿函数实现大小堆
想要大堆改小堆可以直接在代码上面修改，但是要实现大堆，代码又得重新修改。
这里就得用到上面提到的仿函数了。
写两个仿函数，一个实现大堆，一个实现小堆。
大堆实现：
template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}};
小堆实现：
template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};
在写类模板的时候就把仿函数也一起传过去
template<class T, class Container = vector<T>, class Compare = less<T>>5.7 实现自定义类型的优先级队列
定义一个日期类：
class Date{public:friend ostream& operator<<(ostream& _cout, const Date& d);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);}private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}用priority_queue来实现日期排序：
但是如果给的是指针：
传地址每次给的结果不一样。
new不能保证每次new的地址都比前面的大，这里就得重新写一个仿函数。
class GreaterPDate{public:bool operator()(const Date* p1, const Date* p2){return *p1 > *p2;}};这个时候传地址就不会在变了：
所以说仿函数控制比较逻辑，可以控制用什么去比较。
6. 附模拟实现代码
#pragma once#include<vector>namespace bit{template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){ std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};}有问题请指出，大家一起进步！！！
