手机网站做多宽的图片,微信工作平台开发,公司官网如何更新网站,后台html模板目录 优先级队列priority_queuepriority_queue的模拟实现仿函数 优先级队列priority_queue
优先级队列priority_queue是一种容器适配器#xff0c;根据严格的弱排序标准#xff0c;它默认第一个元素总是它所包含的元素中最大的
优先级队列默认使用vector作为底层存储数据的… 目录 优先级队列priority_queuepriority_queue的模拟实现仿函数 优先级队列priority_queue
优先级队列priority_queue是一种容器适配器根据严格的弱排序标准它默认第一个元素总是它所包含的元素中最大的
优先级队列默认使用vector作为底层存储数据的容器在vector上又使用了堆排序的算法对数据进行排序所以priority_queue就是堆。注意priority_queue默认情况下是大堆
priority_queue是存在queue文件中要使用只需要包queue文件就可以 所以以后有需要用到堆的位置我们就不用手动实现一个堆了可以直接使用priority_queue就可以 下面是优先级队列的定义
template class T, class Container vectorT,class Compare lesstypename Container::value_type class priority_queue;第一个模板参数是放在适配器容器内元素的类型 第二个模板参数是适配器默认为vector 第三个模板参数是一个仿函数默认是less为了保证默认是大堆
函数接口说明priority_queue()构造一个空的优先级队列priority_queue (InputIterator first, InputIterator last)用[first,last)迭代器区间构造一个优先级队列empty()判空top( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素
下面我们使用优先级队列尝试一下
void test1()
{priority_queueint pq;pq.push(1);pq.push(6);pq.push(9);pq.push(3);pq.push(0);pq.push(2);while (!pq.empty()){cout pq.top() ;pq.pop();}//输出 9 6 3 2 1 0 cout endl;
}如果我们先实现一个小堆只需要改变第三个模板参数就可以让第三个模板参数为greaterT因为我们指定了第三个模板参数所以我们还需手动显式传第二个模板参数
下面我们实现一个小堆的priority_queue:
void test1()
{priority_queueint,vectorint,greaterint pq;pq.push(1);pq.push(6);pq.push(9);pq.push(3);pq.push(0);pq.push(2);while (!pq.empty()){cout pq.top() ;pq.pop();}//输出 0 1 2 3 6 9cout endl;
}priority_queue的模拟实现
因为优先级队列的底层是堆排序所以我们先完成堆排序中的向下调整和向上调整
void AdjustDown(int parent)
{Compare com;size_t child 2 * parent 1;while (child _con.size()){if (child 1 _con.size() _con[child]_con[child 1]){child;}if (_con[parent] _con[child]){std::swap(_con[child], _con[parent]);parent child;child 2 * parent 1;}else{break;}}
}void AdjustUp(int child)
{Compare com;int parent (child - 1) / 2;while (parent 0){if (_con[parent] _con[child]){std::swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}push函数就是先向底层适配器中插入一个元素然后再调用向上调整法
void push(const T t)
{_con.push_back(t);AdjustUp(_con.size() - 1);}pop函数先把适配器中首元素和尾元素交换然后删除尾元素再调用向下调整法
void pop()
{std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}还有几个实现起来很简单的函数
bool empty()
{return _con.empty();
}const T top()
{return _con[0];
}size_t size()
{return _con.size();
}当前完整代码
namespace my_priority_queue
{templateclass T, class Container std::vectorTclass priority_queue{private:void AdjustDown(int parent){size_t child 2 * parent 1;while (child _con.size()){if (child 1 _con.size() _con[child]_con[child 1]){child;}if (_con[parent] _con[child]){std::swap(_con[child], _con[parent]);parent child;child 2 * parent 1;}else{break;}}}void AdjustUp(int child){int parent (child - 1) / 2;while (parent 0){if (_con[parent] _con[child]){std::swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}public:priority_queue(){}templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){while (first ! last){_con.push_back(*first);first;}for (int i (_con.size() - 1 - 1) / 2; i 0; i--){AdjustDown(i);}}void push(const T t){_con.push_back(t);AdjustUp(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}
此时我们已经实现了一个大堆的优先级队列 那么怎么实现小堆的优先级队列呢当前我们只能去修改向下调整和向上调整中比较大小的部分
这其实挺麻烦的有没有什么方法可以使大堆和小堆的优先级队列可以秒切换呢 答案就是可以使用仿函数 仿函数
仿函数也叫函数对象这个类的对象可以像函数一样使用使一个类的使用看上去像一个函数 其实现就是类中实现一个operator()有了对括号的重载就可以让这个类的对象像函数一样使用
下面就是一个仿函数
class IntLess
{
public:bool operator()(int x,int y){return x y;}};怎么使用仿函数呢毕竟仿函数是一个类所以我们使用时需要先实例化一个对象出来 然后将这个对象像使用函数一样使用 在对象后面加上()该传参就传参
void test2()
{IntLess LessFunc;coutLessFunc(1,2)endl;//仿函数的使用
}LessFunc(1,2)会被处理成LessFunc.operator()(1,2)
接下来用仿函数完善模拟实现的优先级队列
templateclass T
struct Less//首字母大写为了与库中的less区分
{bool operator()(const T t1, const T t2){return t1 t2;}
};templateclass T
struct Greater
{bool operator()(const T t1, const T t2){return t1 t2;}
};首先在模板声明中加一个参数
templateclass T,class Container std::vectorT,class Compare LessT然后然后将向上调整和向下调整中大小判断部分改为仿函数
void AdjustDown(int parent)
{Compare com;//仿函数使用前实例化出一个对象size_t child 2 * parent 1;while (child _con.size()){if (child 1 _con.size() com(_con[child], _con[child 1])){child;}if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent child;child 2 * parent 1;}else{break;}}
}void AdjustUp(int child)
{Compare com;//仿函数使用前实例化出一个对象int parent (child - 1) / 2;while (parent 0){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}
