优先级队列的模拟实现（仿函数）
目录：
1.priority_queue接口的实现（先建大堆）
1.push 加 向上调整的实现
2.pop
3.迭代器区间的构造
2.仿函数
------------------------------------------------------------------------------------------------------------------------------
1.priority_queue接口的实现
1.push 加 向上调整的实现
优先级队列的底层类似于一个数组的东西
我们需要实现向上调整
2.pop
向下调整
3.迭代器区间的构造
那么写了一个迭代器期区间的构造，我们就需要在实现一个的构造函数
我们写了一个显示构造函数，编译器就不会在默认生成构造函数
调用它自己的默认拷贝构造
namespace cdc
{template<class T,class Container =vector<T>>class priority_queue{public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){Adjust_down(i);}}void Adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child>0){if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);Adjust_up(_con.size()-1);}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]){std::swap(_con[child], _con[parent]);parent = child;child = parent *2 +1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//进行向下调整Adjust_down(0);}const T& top() const {return _con[0];}bool empty() const {return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};}2.仿函数
可是我们上面的队列只能排降序（建大堆），这样子就写死了，那么我们怎么才能写灵活呢，能够简单的控制建大堆还是建小堆
仿函数 /函数对象 --类 ，这个类重载operator（）
它的less的类对象可以像函数一样去使用
namespace cdc
{template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class greater{public:bool opeartor()(const T& x, const T& y){return x > y;}};
}int main()
{cdc::less<int> Isfunc;cout << Isfunc(1, 2) << endl;return 0;
}
less 、greater 类 库里都有实现的
3.仿函数优化我们的优先级队列
我们直接用库里的 less 和 greater ，控制我们的比较
namespace cdc
{template<class T,class Container =vector<T>,class Compare=std::less<T>>class priority_queue{public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){Adjust_down(i);}}void Adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child>0){//if (_con[child] > _con[parent])//if (_con[parent]<_con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);Adjust_up(_con.size()-1);}void Adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child<_con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child] , _con[child + 1])){child++;}//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent] , _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent *2 +1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//进行向下调整Adjust_down(0);}const T& top() const {return _con[0];}bool empty() const {return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};}我们less默认是大堆
greater是小堆