C++——优先级队列
1.简介
优先级队列不是传统的队列，它不是先进先出，它是让优先级高的先出。
实际上它就是堆。
注意：优先级队列不需要单独包含头文件，它放在queue这个头文件中，使用时包含queue的头文件即可，#include<queue>
2.使用
2.1大堆
void test_priority_queue1()
{//插入删除数据的效率是logN（以2为底）priority_queue<int> pq;//默认它的底层就是大堆pq.push(1);pq.push(9);pq.push(4);pq.push(7);pq.push(3);while (!pq.empty()){//适配器都没有迭代器cout << pq.top() << " ";//出优先级高的数据，默认是大的数据优先级高pq.pop();}//打印结果：9 7 4 3 1cout << endl;
}2.2小堆
void test_priority_queue2()
{//默认使用less，是大堆//使用greater，是小堆//priority_queue<int> pq; //大堆priority_queue<int,vector<int>,greater<int>> pq;//小堆 //注意：想传第三个模板参数时，必须把第二个也传过去pq.push(1);pq.push(9);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}//打印结果：1 3 4 7 9cout << endl;
}除了可以使用vector来做容器，还可以使用deque
因为堆的底层要支持[]，deque也支持[]
所以只要可以使用下标访问，就可以看作完全二叉树，就可以搞成堆
所以deque还是更适合做栈和队列的底层容器，因为它的头、尾操作效率还可以
但是涉及到下标的随机访问，deque就不太适合了
3.模拟实现priority_queue
namespace jxy
{template<class T,class Container=vector<T>>class priority_queue{public:void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;//左孩子的下标//size_t是为了和size函数的返回值类型保持一致while (child < _con.size())//算出来的下标超出了数组的范围，就结束了{if (child + 1 < _con.size() && _con[child + 1] > _con[child])//如果右孩子存在且比左孩子大，就改变孩子的下标{child++;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size()-1);}//pop：删除堆顶的数据，把堆顶的数据和最后一个数据换一下，然后向下调整void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);//从0，也就是根这个位置开始调整}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;//构造、析构、拷贝、赋值通通不需要写};void test_priority_queue1(){priority_queue<int> pq;pq.push(1);pq.push(9);pq.push(4);pq.push(7);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}//打印结果：9 7 4 3 1cout << endl;}
}
4.仿函数
4.1何为仿函数？
//何为仿函数？
class Less
{
public:bool operator()(int x, int y){return x < y;}
};int main()
{Less less;//通常把less称为函数对象//意思是它虽然是一个对象，但是这个对象可以像函数一样使用//也就意味着，一个类只要重载了operator()，它就可以被称为仿函数cout << less(2, 3) << endl;//单看上面一行，会认为less是函数名或是函数指针//但实际上它是一个对象cout << less.operator()(2, 3) << endl;return 0;
}也就意味着，一个类只要重载了operator()，它就可以被称为仿函数
4.2加入模板
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};int main()
{Less<int> less1;//函数对象cout << less1(1, 2) << endl;cout << less1.operator()(1, 2) << endl;Less<double> less2;//函数对象cout << less2(1.1, 2.2) << endl;//仿函数在功能上，是为了替代函数指针return 0;
}4.3仿函数的价值
仿函数在功能上，是为了替代函数指针
priority_queue默认是大堆，那想使用小堆时，怎么办？难道去改底层的代码吗？显然是不合适的。
C语言的qsort，通过函数指针来控制，是升序还是降序。
但函数指针使用起来并不舒服，C++不想使用这种方式来控制priority_queue是大堆还是小堆，所以仿函数，应运而生。
4.3.1加入仿函数模拟实现priority_queue
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;}
};namespace jxy
{template<class T,class Container=vector<T>,class Compare=Less<T>>//这样的话，代码是没有改变的//改变的是Compare的类型，Compare的类型在实例化时可以任意改变//模板的灵活性就体现出来了，传什么类型就是什么类型class priority_queue{public:priority_queue(){}//如果写了迭代器构造，默认构造也要书写//因为写了构造之后，编译器就不会默认生成了//迭代器构造template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//向下调整建堆——O(N)for (int i = (_con.size() - 2) / 2; i >= 0; --i){adjust_down(i);}//如果去复用push那就是向上调整建堆了//时间复杂度——O(NlogN)}void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//二者等价if(com(_con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){Compare com;//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if (child + 1 < _con.size() &&com(_con[child], _con[child + 1])){child++;}//if (_con[child] > _con[parent])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}private:Container _con;};void test_priority_queue1(){priority_queue<int, vector<int>, Less<int>> pq;//大堆//priority_queue<int,vector<int>,Greater<int>> pq;//小堆pq.push(1);pq.push(9);pq.push(4);pq.push(7);pq.push(3);//使用默认的拷贝构造priority_queue<int> pq1(pq);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}//打印结果：9 7 4 3 1cout << endl;}}仿函数更容易写、更容易理解，它是一个类，就可以在模板参数处进行传递，当然也可以在函数参数处传，sort就是这样
而函数指针是个变量，不能在模板参数传，只能传在函数中，比如构造函数
也很像回调
4.3.2关于sort和priority_queue
namespace jxy
{template<class T,class Container=vector<T>,class Compare=Less<T>>class priority_queue{};void test_sort(){//注意，调试时切换成Debugint a[] = { 1,5,9,2,3,5,6,8,5 };//sort(a, a + 9);//默认是升序，使用 less <sort(a, a + 9,greater<int> ());//greater<int> gt;//sort(a, a + 9, gt);}
}
4.4.库中的less和greater
4.5仿函数的另一大应用
4.5.1
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);//不建议把友元直接定义在类里面//友元函数声明定义分离，定义应该定义在全局
private:int _year;int _month;int _day;
};ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}int main()
{jxy::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;//此时是正常的，会打印2018-10-30return 0;
}4.5.2
int main()
{jxy::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;//2018-10-30jxy::priority_queue<Date*> q2;//如果存的是指针q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));cout << *(q2.top()) << endl;return 0;
}
那么有没有什么办法，可以让它就按照日期去比较
1.首先，重载运算符是不可行的，因为它是内置类型，没法去重载运算符
运算符要求至少有一个参数是自定义类型2.我们可以自己写一个所需的仿函数
也就意味着仿函数还给我们留了一个空间，我们可以自己控制类型的比较规则
//struct和class的区别就是默认的访问限定符不一样
struct PDateCompare
{bool operator()(Date* p1,Date* p2){return *p1 < *p2;}
};
//如果不想使用库里面的，想按照特定的方式去比较，那就自己去书写一个类int main()
{jxy::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;//2018-10-30jxy::priority_queue<Date*, vector<Date*>, PDateCompare> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));cout << *(q2.top()) << endl;//我们可以自己写一个所需的仿函数//也就意味着仿函数还给我们留了一个空间，我们可以自己控制类型的比较规则return 0;
}5.练习题
1.LCR 076. 数组中的第 K 个最大元素 - 力扣（LeetCode）