仿函数本质上是一个类的对象模拟实现一个函数的行为，就是在类中实现operator()函数，这个类有类似函数的行为，由仿函数类创建的对象称为仿函数对象，在优先级队列中，通过调用不同的仿函数，可以实现不同类型的优先级队列，以及可以控制优先级排序规则（大堆，小堆）。
以优先队列（priority_queue）为例
//仿函数类
template
struct Less
{
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
二.容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。而优先级队列就是由其它容器（如：vector，List等）进行包装而产生的另一个接口。
三.优先级队列的模拟实现 3.1 什么是优先级队列1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的或是最小的。
2. 优先级队列类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
（1）empty()：检测容器是否为空
（2）size()：返回容器中有效元素个数
（3）front()：返回容器中第一个元素的引用
（4）push_back()：在容器尾部插入元素
（5）pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
3.2 成员变量由于优先级队列是一个容器适配器，所以它的成员变量是一个STL容器类
private: Container _Con;3.3 向上/向下排堆函数（adjustup()/adjustdown()函数）
建堆的具体过程讲解：
https://blog.csdn.net/weixin_41368411/article/details/123582596?spm=1001.2014.3001.5501
代码实现如下：
//向上调整建堆
void adjust_up(size_t child)
{
compare com;
size_t parent = (child - 1)/ 2;
while (child > 0)
{
if (com(_Con[child], _Con[parent]))
{
std::swap(_Con[child], _Con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整建堆
void adjust_down(size_t parent)
{
compare com;
size_t child = parent * 2 + 1;
while (child < size())
{
if (child + 1 < size() && com(_Con[child + 1], _Con[child]))
{
child = child + 1;
}
if (com(_Con[child], _Con[parent]))
{
std::swap(_Con[child], _Con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
3.4迭代器实现构造函数
注意：在默认情况下优先级队列是一个大堆，这里可以通过控制仿函数来实现小堆的创建
代码实现：
//利用迭代器完成构造函数 templatepriority_queue(Inputiterator first, Inputiterator last) :_Con(first, last) { for (int i = _Con.size() / 2 - 1; i >= 0; i--) { adjust_down(i); } }
代码测试：
3.5优先级队列实现日期类的排序3.5.1 模板的特化
通常情况下，使用模板可以实现一些与类型无关的代码，但对于一些特殊类型的可能会得到一些错误的结果，此时，就需要对模板进行特化。即：在原模板类的基础上，针对特殊类型所进行特殊化的实现方式。模板特化中分为函数模板特化与类模板特化。
在优先级队列中，如果我们要实现对于某一个类的特殊的比较方式，我们可以使用模板的特化，来实现该功能，比如，我们在优先级队列类的创建的过程中，对仿函数类模板的特化，就可以实现堆日期类的比较。
templatestruct Less { bool operator()(const T& x, const T& y) const { return x < y; } }; template<> struct Less { bool operator()(const Data& x, const Data& y) const { return x < y; } };
3.5.2 日期类代码实现
//日期类
class Date
{
public:
Date(int year, int month, int day)
:_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);
}
int _year;
int _month;
int _day;
};
//打印输出日期对象的内容
ostream& operator<< (ostream& out, const Date& d)
{
out << d._year << "-" << d._month << "-" << d._day; return out;
}
template
struct Less
{
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
template<>
struct Less
{
bool operator()(const Date& x, const Date& y) const
{
return x < y;
}
};
template
struct Greater
{
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
};
//模板特化
template<>
struct Greater
{
bool operator()(const Date& x, const Date& y) const
{
return x > y;
}
};
3.5.3 代码测试
四.优先级队列的完整实现 代码：templatestruct Less { bool operator()(const T& x, const T& y) const { return x < y; } }; template struct Greater { bool operator()(const T& x, const T& y) const { return x > y; } }; template , class compare = Greater > class priority_queue { public: priority_queue() { } //利用迭代器完成构造函数 template priority_queue(Inputiterator first, Inputiterator last) :_Con(first, last) { for (int i = _Con.size() / 2 - 1; i >= 0; i--) { adjust_down(i); } } //向上调整建堆 void adjust_up(size_t child) { compare com; size_t parent = (child - 1)/ 2; while (child > 0) { if (com(_Con[child], _Con[parent])) { std::swap(_Con[child], _Con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //向下调整建堆 void adjust_down(size_t parent) { compare com; size_t child = parent * 2 + 1; while (child < size()) { if (child + 1 < size() && com(_Con[child + 1], _Con[child])) { child = child + 1; } if (com(_Con[child], _Con[parent])) { std::swap(_Con[child], _Con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //迭代器 typename Container::iterator begin() { return _Con.begin(); } typename Container::const_iterator end() { return _Con.end(); } //在堆中插入数据，需要采用自下而上的建堆方法 void push(const T& val) { _Con.push_back(val); adjust_up(_Con.size() - 1); } //堆顶数据 const T& Top() { return _Con[0]; } //堆中的数据个数 size_t size() { return _Con.size(); } //删除堆顶数据 void pop() { std::swap(_Con[0], _Con[size() - 1]); _Con.pop_back(); adjust_down(0); } //判断该堆中数据是否为空 bool empty() { return _Con.empty(); } private: Container _Con; };
