网站建设站,百度关键词刷排名教程,用flash做游戏下载网站,怎样用网站做淘宝推广目录#xff1a; 1.priority_queue接口的实现#xff08;先建大堆#xff09; 1.push 加 向上调整的实现 2.pop 3.迭代器区间的构造 2.仿函数 3.仿函数优化我们的优先级队列
-------------------------------------------------------------------------------------------…目录 1.priority_queue接口的实现先建大堆 1.push 加 向上调整的实现 2.pop 3.迭代器区间的构造 2.仿函数 3.仿函数优化我们的优先级队列
------------------------------------------------------------------------------------------------------------------------------ 1.priority_queue接口的实现 1.push 加 向上调整的实现 优先级队列的底层类似于一个数组的东西 我们需要实现向上调整 2.pop 向下调整 3.迭代器区间的构造 那么写了一个迭代器期区间的构造我们就需要在实现一个的构造函数
我们写了一个显示构造函数编译器就不会在默认生成构造函数
调用它自己的默认拷贝构造 namespace cdc
{templateclass T,class Container vectorTclass priority_queue{public:priority_queue(){}templateclass InputIteratorpriority_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 (child0){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
{templateclass Tclass less{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass greater{public:bool opeartor()(const T x, const T y){return x y;}};
}int main()
{cdc::lessint Isfunc;cout Isfunc(1, 2) endl;return 0;
}less 、greater 类 库里都有实现的 3.仿函数优化我们的优先级队列 我们直接用库里的 less 和 greater 控制我们的比较
namespace cdc
{templateclass T,class Container vectorT,class Comparestd::lessTclass priority_queue{public:priority_queue(){}templateclass InputIteratorpriority_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 (child0){//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是小堆
