前言：这篇文章我们继续来分享一个c++的容器——优先级队列。
一.理解优先级
何为优先级一说？实际上就是有顺序的意思。
优先级队列，即有顺序的队列，是一个无需我们自己进行排序操作，在数据传入时就会由容器自己排好序的队列。
先来看实例：
使用该队列，同样需要包含头文件#include<queue>。
在默认情况下，优先级队列是按照从大到小排序的，而在数据结构中，也有一个能够自主排序，没错，就是堆。从大到小的顺序，也就是大堆。
那么如果想要实现小堆，又该怎么办呢？只需要增加一下模版参数：
至于为什么这样写就是小堆，我们再接下来的模拟实现中进行解答。
二.基本框架
堆可以通过父节点或字节点的下标来互相找到对方的下标，所以一般情况都以数组为模板。
template <class T,class Container = vector<T>>
class priority_queue
{
public:
//向上调整
void adjust_up(size_t child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
child = parent;
int parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
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])
{
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);
}
//删除
void pop()
{
swap(_con[_con.size() - 1], _con[0]);
_con.pop_back();
adjust_down(0);
}
//队头元素
T& top()
{
return _con[0];
}
//数据个数
size_t size()
{
return _con.size();
}
//判空
bool empty()
{
return _con.empty();
}
private:
Container _con;
};这里我们直接给出优先级队列的基本常规操作，本质就是堆的各种操作，不再一一分享。
而我们要重点分享的，就是如何切换升降序。
三.仿函数
从名字就能看出，这是一个可以冒充函数的家伙，先来看例子：
template <class T>
class less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};这段代码不难理解，在一个类中声明了一个运算符重载函数，这个函数能够进行大小比较。
再来看这段代码，能够发现我们能够直接通过一个对象来进行两个数据之间的比较。
这就是所谓的仿函数。
上述仿函数是进行“小于”比较，同样我们也可以在创造一个仿函数来进行“大于”比较。
如此一来，我们便可以通过类模板将这两个仿函数用于排序比较。
四.实现可选优先级
直接看代码：
//小于比较
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;//注意
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))//注意
{
swap(_con[child], _con[parent]);
child = parent;
int 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 (com(_con[parent], _con[child]))//注意
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}其中less为小于比较的类，而greater为大于比较的类。
而后我们通过使用类模板参数compare将两者整合在一起，因为库里的优先级队列默认即为大堆，所以我们使用缺省参数默认为less。
前边已经提到，使用仿函数，就是使用对应类的对象，所以我们需要创建compare类的对象com，并传入比较内容进行比较。
这里要注意两个比较数据的先后位置，要按照到底是谁大于谁而传入正确的先后顺序。
随后就可以按照排序要求对类型进行更改，按照我们的代码方式，less为降序，greater为升序。
