前言
本文章讲解C++STL的容器适配器：priority_queue的实现，并实现仿函数控制priority_queue底层。
一、priority_queue的底层实现
priority_queue叫做优先级队列，它的底层结构是堆，在库中，默认生成的是大堆
在库的实现中，使用vector作为该优先级队列的适配容器。
由于priority_queue也是一个适配器，所以它的接口函数也可以对其他容器的函数进行封装使用。
下面来对priority_queue进行模拟实现。
#pragma once //优先级队列底层是堆，heap namespace bit { //仿函数 template<class T> class Less { public: bool operator()(const T& t1, const T& t2) { return t1 < t2; } }; template<class T> class Greater { public: bool operator()(const T& t1, const T& t2) { return t1 > t2; } }; //类名不是类型 template<class T, class Container = vector<T>, class Compare = Less<T> > //默认大堆 class PriorityQueue { //com是一个仿函数 Compare com; void AdjustDown(int parent) { int child = parent * 2 + 1; while (child > 0) { //可能右孩子存在且大于左孩子 if (child + 1 < _con.size() && com(_con[child],_con[child + 1])) { ++child; } //如果孩子存在且孩子大于父亲，交换 if (child < _con.size() && com(_con[parent],_con[child])) { swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void AdjustUp(int child) { Compare com; //类名实例化类对象，该类型是一个仿函数，实例化的com可以调用仿函数的比较方法 //记录父亲的下标 int parent = (child - 1) / 2; while (child > 0) { if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); } child = parent; parent = (child - 1) / 2; } } public: PriorityQueue() {} //默认建大堆 template<class InputIterator> PriorityQueue(InputIterator first, InputIterator end) { //插入数据 while (first != end) { _con.push_back(*first); ++first; } //向下调整建堆 for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i) { AdjustDown(i); } } void push(const T& val) { //插入元素 _con.push_back(val); //然后向上调整 AdjustUp(_con.size() - 1); } void pop() { //1.堆顶和堆尾交换 swap(_con[0], _con[_con.size() - 1]); //2.删除堆尾 _con.pop_back(); //3.向下调整，恢复堆 AdjustDown(0); } T& top() { return _con[0]; } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con;
注解：
- 1.在进行构造时，我们使用迭代区间进行构造
- （1）向空间中插入数据
- （2）向下调整建堆，建N个数据，从第一个非叶子节点开始进行建堆，每次都向下调整，时间复杂度O(N)。
push函数的实现：
向堆尾插入一个元素，插入的元素可能会改变堆的结构，所以我们需要将该元素向上调整，以维护堆的特性。
pop函数的实现：
删除堆顶元素，首先将堆顶元素和堆的最后一个元素进行交换，然后进行尾删，删除后原来的堆尾的元素现在在堆顶，我们需要将其进行向下调整以维持堆的状态。
empty函数：
判断堆是否为空即可。
size函数：
计算堆的元素个数。
top函数：
取堆顶元素，也就是取第一个元素。
priority_queue容器的作用：有需要使用堆的地方就可以使用该容器。
二、使用仿函数控制priority_queue的底层
什么是仿函数？
仿函数：仿造的函数，它并不是一个真正意义上的函数。能够重载operator()，内部实现自己想要的方法，然后实例化出一个方法对象，调用该对象作为参数，此时就可以调用该方法类对象内部实现的operator()方法了。
由于库中的优先级队列的底层结构是堆，且默认是大堆，我们在模拟实现和使用时，如果遇到需要使用小堆的场景，需要改变的东西很多，比如向上调整算法和向下调整算法的比较方法。
现在我们需要指定一个方法，这个方法可以由我们控制，从而实现大小堆。
仿函数：
//仿函数 template<class T> class Less { public: bool operator()(const T& t1, const T& t2) { return t1 < t2; } }; template<class T> class Greater { public: bool operator()(const T& t1, const T& t2) { return t1 > t2; } };
这里实现了两个类，并重载了一个比较方法。
在priority_queue模板的实现中，我们可以多传递一个模板参数：class Compare，也就是多传递一个比较方法。然后我们自己写一个比较方法传递过去，然后在priority_queue的实现中实例化一个方法对象来控制堆的生成。
总结
本文章讲解了仿函数控制priority_queue容器的底层实现的过程以及priority_queue的底层实现。
只要有堆的地方就可以使用priority_queue容器。
