目录
前言：
1 优先级队列的使用
2 优先级队列的实现
3 仿函数
前言：
栈和队列相对其他容器来说是比较简单的，在stl里面，有一种容器适配器是优先级队列（priority_queue），它也是个队列，但是不大像队列，本文中简略介绍如何使用和模拟实现它。
1 优先级队列的使用
要使用，先文档：
文档黑体第一句话就是，优先级队列是一种容器配置器，容器配置器是？电脑有电源适配器，起到提供电源的作用，但是这个适配器不是充电器，即充电的时候，电源来自于电线，但是我们不能直接拿电线充电吧？这时候适配器就有用了，通过封装，使得两边达到一个配合的效果，容器配置器同理。当然这不是重点。
模板是必要的，模板参数有3个，参考栈和队列，第二个参数是底层用的哪种容器进行实现的，这里的默认是使用的顺序表，第三个参数是仿函数，后面介绍。
那么在来看看成员函数：
很少是吧，可以说成员函数和队列没有什么差别，所以我们现在简单使用一下：
int main()
{
priority_queue<int> q1;
q1.push(2);
q1.push(1);
q1.push(4);
q1.push(3);
q1.push(5);
cout << q1.size() << endl;
while (!q1.empty())
{
cout << q1.top() << " ";
q1.pop();
}
cout << endl;
cout << q1.size() << endl;
return 0;
}
使用很简单，但是打印的结果却，，有点奇怪？
这就是优先级队列的特殊之处了，我们并没有对它进行排序，但是打印出来是默认有序的，这是因为它的本质是堆，而模板参数第三个仿函数的参与，决定了它是大堆还是小堆，默认是升序的，可以理解为升序状态下谁最小谁优先级最高，所以先被打印。
但是实际上，不用管那么多，就把它认为是堆就ok了，所以我们实现的时候需要实现向上调整算法和向下调整算法。
对于仿函数我们放在实现了80%在介绍。
2 优先级队列的实现
我们需要实现以下几个接口：
empty,size,push,pop,top，接口不多，另外还要实现向上调整算法和向下调整算法。
优先级队列的一般结构为：
template <class T,class container = vector<T>>
class priority_queue
{
public:
private:
container _con;
};模板的第三个参数先不急。
简单的几个接口我们一股脑实现就完事了：
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
bool empty()
{
return _con.empty();
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
size_t size()
{
return _con.size();
}
const T& top()
{
return _con[0];
}这部分是没什么难度的。
随机要实现的是push和pop，这里提问，为什么默认的底层实现是vector呢？
因为堆的本质，就是一块连续的空间，我们只是把它抽象为了完全二叉树。
push数据之后，堆本身的结构被破坏了，所以我们需要向上调整数据，在数据结构初级的时候，已经介绍过两种算法，这里过一下就Ok：
向上调整算法是通过孩子节点和父节点的值进行比较，然后交换位置，可能有点倒反天罡，谁的值大谁就当爸爸？我们知道孩子节点的下标之后，父节点的下标就是（孩子下标 - 1） / 2，如果不熟悉可以拿图推演一下，最后一次交换的时候，孩子节点的下标变成了父节点的下标，所以判断条件应该是孩子节点的下标是否合法，即是否大于0：
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if(_con[parent] < _con[child])
{
swap(_con[parent],_con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}此时push的的准备工作就做好了，插入，调整，完成：
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}与之对应的是pop，pop对应的准备工作是向下调整算法，向下调整算法有几个需要注意的点就是，我们建大堆，那么就要在孩子节点中找到两个孩子中较大的那一个，除此之后，不是所有的节点都有两个子节点，所以我们需要保证孩子 + 1不小于size，这是基础工作，随机就是比较大小，谁大谁就往上：
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{
child++;
}
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}pop的准备工作也是完毕了，那么pop就行，对于堆部分有些遗忘的同学就会想为什么涉及到向下调整，因为删除，为了效率和不破坏堆的结构，我们的措施是首尾交换，向下调整。
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}3 仿函数
仿函数是本文的重点，我们需要先知道什么是仿函数？
先看一段这样的代码：
template <class T>
struct Less
{
bool operator()(const T& a,const T& b)
{
return a > b;
}
};
void Func(int ,int)
{
cout << endl;
}
int main()
{
Less<int> Fun;
Fun(1,2);
Func(1,2);
return 0;
}如果说只看主函数的代码，就会容易觉得，这不就是两个函数调用吗？仿函数仿函数，顾名思义，模仿函数，因为调用的时候挺像函数的，但是实际上，它是一个类，这个类实例化对象，使用重载后的()，我们称这个过程叫做仿函数调用，仿函数实际上只有一个东西，就是重载的()。
重载的()没有其他东西，只有比较，对于内置类型我们可以直接比较，对于自定义类型我们可能要重载一下> 或者 <。
所以，仿函数是个类，类里面的函数是重载的()，一般是两个参数，用于比较使用。
所以我们在向上调整算法和向下调整算法的实现里面的比较，就可以用仿函数完成，进而控制升序降序，那么我们就还要写两个类：
//仿函数
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 = greater<T>>
void adjust_up(size_t child)
{
compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if(com(_con[parent] , _con[child]))
{
swap(_con[parent],_con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
compare com;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
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;
}
}
}向下调整算法这里有个注意的，if(child + 1 < _con.size() && com(_con[child], _con[child + 1]))，第一个判断条件放在前面是最好的，因为越界了不用了比较了，代码逻辑更严密。
但是这里使用了仿函数好像也没有什么特别的，无非就是用了一个像函数调用一样的类而已，为什么不用C语言中qsort里面的函数指针呢？
在C++里面函数指针并不常用，难写不说，代码的可移植性还不高，目前我们针对的内置类型使用的仿函数效果不明显，我们引入一个日期类，一个自定义类型，进行日期的比较。
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);
}
private:
size_t _year;
size_t _month;
size_t _day;
};对于自定义类型的比较重载已经写在了类里面，现在直接比较就可以了：
class DateGreater
{
bool operator()(const Date& d1, const Date& d2)
{
return d1 > d2;
}
};
class DateLess
{
bool operator()(const Date& d1, const Date& d2)
{
return d1 < d2;
}
};void Test2_priority_queue()
{
priority_queue<Date> q1;
q1.push({ 2024, 4, 17 });
q1.push({ 2024, 4, 18 });
q1.push({ 2024, 4, 19 });
q1.push({ 2024, 4, 20 });
cout << q1.size() << endl;
while (!q1.empty())
{
cout << q1.top() << " ";
q1.pop();
}
cout << endl;
}对比淘宝，淘宝的的排序，比如综合评分排序，销量排序等，用户点击对应按钮，系统就会调用对应的函数，使用的就是仿函数，函数指针在C++里面不太常用，它的类型和变量名混杂一起，看起来不太舒服。
仿函数的一般使用差不多了，但是如果我们给优先级队列里面存放日期类的指针，但是相比较日期类的大小怎么办呢？
void Test3_priority_queue()
{
priority_queue<Date*, vector<Date*>> q1;
q1.push(new Date(2024,5,20));
q1.push(new Date(2024,5,21));
q1.push(new Date(2024,5,22));
q1.push(new Date(2024,5,23));
while (!q1.empty())
{
cout << *(q1.top()) << " ";
q1.pop();
}
cout << endl;
}比如这样，里面都是指针，我们push的也是new出来的指针，我们使用的仿函数是：
class DateGreater
{
bool operator()(const Date& d1, const Date& d2)
{
return d1 > d2;
}
};
class DateLess
{
bool operator()(const Date& d1, const Date& d2)
{
return d1 < d2;
}
};那么这个仿函数就不可以了，比较出来的都是随机结果，这是因为new出来的地址都是随机的，而默认的是比较的指针，打印出来的是对应的日期，所以结果一会儿是对的一会儿是错的，这是因为仿函数的错误使用，我们应该解引用之后再进行比较，这里就要另外提供一个仿函数了：
class PDateGreater
{
public:
bool operator()(Date* d1, Date* d2)
{
return *d1 > *d2;
}
};光提供了还不行，我们还要显式调用：
void Test3_priority_queue()
{
priority_queue<Date*, vector<Date*>,PDateGreater> q1;
q1.push(new Date(2024,5,20));
q1.push(new Date(2024,5,21));
q1.push(new Date(2024,5,22));
q1.push(new Date(2024,5,23));
while (!q1.empty())
{
cout << *(q1.top()) << " ";
q1.pop();
}
cout << endl;
}这样就是完美的了。仿函数的简单介绍就到这里。
感谢阅读！
