2. 仿函数
1. 仿函数的概念
在上文中，我们看到priority_queue类模板中，有三个模板参数，其中第三个就是仿函数。
仿函数到底是什么呢？
仿函数(functors)，也叫函数对象(function objects)，是STL六大组件中的一部分，这里我们没办法一次性讲完它，所以就基于priority_queue的实现稍微介绍一下。
实际上，就实现意义而言，函数对象这个名字更加贴切：一种具有函数特质的对象。但是，仿函数似乎能更加符合的描述他的行为。所以这里我们就采用仿函数这种叫法。
在学习STL之前我们就已经了解了泛型编程的概念，C++引入了模板让我们的编程能够随意的控制数据类型，现在引入了仿函数的概念，让我们能够控制逻辑。
那么现在让我们见见仿函数：
这两个就是我们在priority_queue的参数列表中可能用到的仿函数。
可以看到，在使用的时候，实际上类似一个函数的调用，因此被称为仿函数
2.尝试实现仿函数
仿函数的本质就是一个运算符重载operator()，重载的是函数调用的运算符。由于仿函数本身也就是一个类模板，所以我们的实现如下
template<class T> class less { public: bool operator()(const T& x, const T& y)//less和greater需要实现的就是一个比较，所以这里的返回值是bool类型 { return x < y; } }; template<class T> class greater { public: bool operator()(const T& x, const T& y) { return x > y; } };
这样就算是实现了less和greater的仿函数。
这里只是稍微提了一下仿函数的概念，仿函数毕竟是STL六大组件之一，其中包含的东西还有很多，我们对仿函数的学习还在路上
3.priority_queue的模拟实现
有了上述只是的铺垫，现在我们已经有了模拟实现priority_queue的能力，那么just do it。
1.priority_queue的结构
首先，对于函数模板的设计，我们和库里面对其，给了三个参数，分别表示参数存入容器的参数类型，容器类型和仿函数，其中默认的仿函数是less，建大堆。
template<class T, class Container = std::vector<T>, class Compare = less<T>> class priority_queue { public: //... private: Container _con; };
2. 接口实现
按照我们之前在【数据结构】树与二叉树实现堆的经验，一定需要实现的两个接口是向上调整和向下调整，这也是整个堆的核心接口，所以我们就先着重实现这两个功能性接口，这两个接口实现完成之后，其他的结构性接口都很容易实现啦。
1.向下调整算法
这里，我们以小堆为例(在这里偷个懒：小堆的图有以前画过的)，我们需要做的事情就是找到两个孩子中较小的，然后与父节点比较大小，如果父节点大于子节点就执行交换，然后原来的子节点成为新的父节点，再次进行上述步骤。直到符合堆的结构
void adjust_down(size_t parent) { Compare cmp;//实例化仿函数 int minchild = 2 * parent + 1; while (minchild < _con.size()) { if (minchild + 1 < _cin.size() && cmp(_con[minchild], con[minchild + 1]))//使用仿函数找到符合条件的子节点 { minchild++; } if (cmp(_con[parent], _con[minchild]))//判断是否满足堆结构 { std::swap(_con[parent], _con[minchild]); //父子节点迭代 parent = minchild; minchild = 2 * parent + 1; } } }
2. 向上调整算法
这里向上调整的操作，从指定的孩子节点位置开始，和父节点比较，判断是否满足堆结构，如果不满足，就交换父子节点，然后原来的父节点编程子节点，再次进行上述操作，直到满足堆结构为止。
void adjust_up(size_t child) { Compare cmp;//实例化仿函数 size_t parent = (child - 1) / 2; while (child > 0) { if (cmp(_con[parent], _con[child])) { std::swap(_con[parent], _con[child]); //父子迭代 child = parent; parent = (child - 1) / 2; } } }
3.构造函数
构造函数分为无参的构造和迭代器区间构造
//无参的构造函数 priority_queue() {} //迭代器区间构造 template<class InputIterator> priority_queue(InputIterator first, InputIterator last) _con(first, last) { //从最后一个父节点的位置开始向下调整建堆，效率最高 for (int i = (_con.size() - 1 - 1) / 2; i <= 0; --i) { adjust_down(i); } }
4.修改数据
priority_queue的数据修改只有push和pop两种情况
push数据就直接尾插，然后向上调整堆，直到满足堆的结构即可，pop数据就交换堆顶数据和最后一个数据，然后容器pop_back，然后向下调整直到剩余数据满足堆结构即可
void push(const T& val) { _con.push_back(val);//尾插数据 adjust_up(_con.size() - 1);//向上调整堆结构 } void pop() { swap(_con[0], _con[_con.size() - 1]);//交换堆顶和堆内最后一个元素 _con.pop_back;//容器尾删 adjust_down(0);//向下调整堆结构 }
5.获取数据
剩下的接口就直接复用容器提供的接口即可
bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } const T& top() const { return _con[0]; }
