购买一个网站域名需要多少钱网址价格

当前位置： 首页 > news >正文

购买一个网站域名需要多少钱,网址价格,做网站哪里比较好,自己制作网页查询系统目录 一.认识priority_queue 二. priority_queue的使用 三.仿函数 1.什么是仿函数 2.控制大小堆 3.TopK问题 四.模拟实现priority_queue 1.priority_queue的主要接口框架 2.堆的向上调整算法 3.堆的向下调整算法 4.仿函数控制大小堆 五.priority_queue模拟实现整体代码和测…目录 一.认识priority_queue 二. priority_queue的使用 三.仿函数 1.什么是仿函数 2.控制大小堆 3.TopK问题 四.模拟实现priority_queue 1.priority_queue的主要接口框架 2.堆的向上调整算法 3.堆的向下调整算法 4.仿函数控制大小堆 五.priority_queue模拟实现整体代码和测试 一.认识priority_queue priority_queue—-reference

1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。 4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素
2. 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。 二. priority_queue的使用 优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。 函数声明接口说明priority_queue()/priority_queue(first,last)构造一个空的优先级队列empty( )检测优先级队列是否为空是返回true否则返回 falsetop( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素 测试 #includequeue #includeiostream using namespace std; int main() {//够一个空的优先级队列priority_queueint pri_q;//插入数据pri_q.push(2);pri_q.push(27);pri_q.push(25);pri_q.push(244);pri_q.push(212);pri_q.push(9);//连续取出堆顶数据打印while (!pri_q.empty()){cout pri_q.top() ;pri_q.pop();}return 0; } 三.仿函数 如果我们像控制优先级队列是大堆排还是小堆排就需要我们使用放仿函数去控制。 1.什么是仿函数 首先仿函数是一个类它重载了括号运算符在使用的时候定义出对象就像函数一样使用。 例如 //仿函数 templateclass T struct Add {int operator()(int e1, int e2){return e1 e2;} };int main() {Addint add;cout add(10, 20) endl;return 0; } 2.控制大小堆 在头文件functional中包含了两个仿函数,less和granter。 less是判断小于的仿函数对应堆排出来是大堆granter是判断大于的仿函数对应堆排出来是小堆。 #includequeue #includefunctional #includeiostream using namespace std; int main() {//小堆priority_queueint,vectorint,greaterint small_q;//插入数据small_q.push(2);small_q.push(27);small_q.push(25);small_q.push(244);small_q.push(212);small_q.push(9);//连续取出堆顶数据打印while (!small_q.empty()){cout small_q.top() ;small_q.pop();}cout endl;//大堆priority_queueint, vectorint, lessint big_q;//插入数据big_q.push(2);big_q.push(27);big_q.push(25);big_q.push(244);big_q.push(212);big_q.push(9);//连续取出堆顶数据打印while (!big_q.empty()){cout big_q.top() ;big_q.pop();}return 0; } 3.TopK问题 这个问题我们在数据结构二叉树堆的部分已经详细的分析了感兴趣的可以去看看数据结构—二叉树—堆 四.模拟实现priority_queue 1.priority_queue的主要接口框架 templateclass T, class Continer vectorT class Priority_queue { public://插入数据void push(const T val){_con.push_back(val);//向上调整adjust_up(_con.size() - 1);}//删除数据void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//向下调整adjust_down(0);}//返回栈顶数据const T top(){return _con[0];}//判断栈是否为空bool empty(){return _con.empty();}private:Continer _con;//适配容器默认是vector };2.堆的向上调整算法 堆的插入需要保证插入以后还是一个堆所以这里用到了向上调整算法。 在数组中就是插入一个数在数组的尾上再通过向上调整算法调整到合适的位置。 在以堆的角度来看小堆为例将新插入的值看作孩子与其父亲位置的值比较如果比父亲位置的值还要小那就将该值与父亲位置的值进行交换交换后将父亲位置当作新的孩子继续与其父亲位置的值比较这样一直向上比较并交换直到父亲位置的值比自己小或该位置已经没有父亲了调整结束。 //向上调整算法void adjust_up(size_t child){//1.计算父亲size_t parent (child - 1) / 2;while (child 0){//如果孩子比父亲大就交换否则就直接推出if (_con[parent] _con[child]){swap(_con[parent], _con[child]);//交换之后父亲成为新的孩子继续算新的父亲直到没有孩子了child parent;parent (child - 1) / 2;}else{break;}}} 3.堆的向下调整算法 向下调整算法大堆为例:从第一个结点开始找到其孩子结点中较大的一个与父亲位置进行交换然后将孩子作为新的父亲再次比较和交换直到父亲结点比两个结点的值都大或者已经没有孩子了为止。 //向下调整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[parent] _con[child]){swap(_con[child], _con[parent]);}else{break;}//孩子成为新的父亲继续算出新的孩子parent child;child parent * 2 1;}} 4.仿函数控制大小堆 //比较小于的仿函数控制大堆templateclass Tstruct less{bool operator()(const T val1,const T val2){return val1 val2;}};//比较大于的仿函数控制小堆templateclass Tstruct grater{bool operator()(const T val1, const T val2){return val1 val2;}};templateclass T, class Continer vectorTclass Compare lessT//默认大堆 class Priority_queue { public:Compare com;//插入数据void push(const T val){_con.push_back(val);//向上调整adjust_up(_con.size() - 1);}//删除数据void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//向下调整adjust_down(0);}//返回栈顶数据const T top(){return _con[0];}//判断栈是否为空bool empty(){return _con.empty();}private:Continer _con;//适配容器默认是vector };五.priority_queue模拟实现整体代码和测试 Queue.hpp: templateclass T, class Continer vectorT,class Compare lessTclass Priority_queue{public:Compare com;void push(const T val){_con.push_back(val);adjust_up(_con.size()-1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private://向上调整算法void adjust_up(size_t child){size_t parent (child - 1) / 2;while (child 0){if (com(_con[parent] , _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}//向下调整void adjust_down(size_t parent){size_t child parent * 2 1;while (child_con.size()){if (child 1 _con.size() com(_con[child],_con[child 1])){child;}if (com(_con[parent] , _con[child])){swap(_con[child], _con[parent]);}else{break;}parent child;child parent * 2 1;}}private:Continer _con;}; } main: #includeiostream #includevector #includelist using std::vector; using std::list; using std::cout; using std::endl; using std::swap;#includeQueue.hpp using namespace Qikun;int main() {//小堆Priority_queueint,std::vectorint, greaterint small_q;//插入数据small_q.push(2);small_q.push(27);small_q.push(25);small_q.push(244);small_q.push(212);small_q.push(9);//连续取出堆顶数据打印std::cout 小堆;while (!small_q.empty()){cout small_q.top() ;small_q.pop();}cout endl;//大堆Priority_queueint, vectorint, lessint big_q;//插入数据big_q.push(2);big_q.push(27);big_q.push(25);big_q.push(244);big_q.push(212);big_q.push(9);//连续取出堆顶数据打印cout 大堆;while (!big_q.empty()){cout big_q.top() ;big_q.pop();}return 0; }