网站页面优化,关键词网站查询,北京王府井书店网上商城,模板建站与仿站哪个更好文章目录 前言优先级队列的结构优先级队列的模拟实现仿函数 最终代码 前言
什么是优先级队列#xff0c;从该名中可以知道他一定有队列的一定属性#xff0c;即先入先出(LILO)#xff0c;而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进… 文章目录 前言优先级队列的结构优先级队列的模拟实现仿函数 最终代码 前言
什么是优先级队列从该名中可以知道他一定有队列的一定属性即先入先出(LILO)而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进行出队这就是优先级队列 而在数据结构中有一个支持该操作的结构 - 堆( heap ); 而在STL中这个优先级队列( priority_queue )也正是堆 优先级队列的结构
既然优先级队列的结构是堆那想必结构上也不难 堆的结构是以顺序表为基础从而实现完全二叉树的结构
从该容器的接函数接口中也可以知道实际上它就是个堆 优先级队列的模拟实现
优先级队列priority_queue为一个类模板容器 且同STL中的栈stack与队列queue一样都为适配器模式的容器即以某个容器为基础
template class T, class Container vectorT,class Compare lesstypename Container::value_type class priority_queue; 其模板参数有三个分别为 class T 容器所存储的数据类型 T class Container vectorT 容器适配器且定缺省参数默认为 vector T class Compare lesstypename Container::value_type 一个用来比较大小的仿函数给定缺省参数默认为 less 该仿函数在标准库std中
根据文档中的信息来看优先级队列主要的几个接口也正是数据结构中堆应有的结构
#pragma once #includeiostream#includevector#includeassert.husing namespace std;namespace my_priority{//命名空间templateclass T,class Container std::vectorT//暂未设置仿函数class priority_queue{//总体框架public:void push(const T val){//增_con.push_back(val);adjust_up(_con.size()-1);}void pop(){std::swap( _con[_con.size()-1],_con[0]);//删_con.pop_back();adjust_down(0);}bool empty(){//判空return _con.empty();}size_t size(){//返回大小return _con.size();}const T top()const{//返回堆顶assert(!_con.empty());return _con[0];}void swap(priority_queue con){//交换if(_con!con._con)_con.swap(con._con);}private://必要函数 - 向上调整向下调整void adjust_up(size_t child){size_t parent child;while(parent0){parent (child-1)/2;if(_con[parent]_con[child]){std::swap(_con[parent],_con[child]);}child parent;}}void adjust_down(size_t parent){Compare comfunc;size_t child parent*21;while(child_con.size()){if(child1_con.size()_con[child]_con[child1]){child;}if(_con[parent]_con[child]){std::swap(_con[parent],_con[child]);}parent child;child parent*21;}}Container _con; //容器适配器所实例化的对象当前代码为vectorint};但是在库中模板参数共有三个具体的第三个仿函数到底是什么 仿函数
仿函数也被称为函数对象 即一个可以使用函数功能的类本质上就是在类中重载了operator(); 举个简单的例子当我们想要写一个能将两个数进行相加的仿函数即可以这么写
struct Add{int operator()(int a,int b){return ab;}
}
int main()
{Add addfunc;int ret addfunc(1,2);//仿函数的调用ret Add() (1,2);//利用匿名对象return 0;
}同理也可以根据该方法写一个比较两个对象大小的仿函数 为了能接受多种类型的数据进行比较也可以将其设置为类模板
templateclass T
struct less{bool operator()(const T a,const T b){return ab;} 这也就是在实现当中缺失的模板参数仿函数 由于优先级队列priority_queue的大小根堆属性是由其中的向上调整算法adjust_up与向下调整算法adjust_down来决定的建堆以及堆的调整所以只要将对应的比较大小换成仿函数即可 最终代码
#pragma once #includeiostream#includevector#includeassert.husing namespace std;namespace my_priority{templateclass Tstruct less{bool operator()(const T v1,const T v2){return v1v2;}};templateclass Tstruct greater{bool operator()(const T v1,const T v2){return v1v2;}};templateclass T,class Container std::vectorT ,class Compare lessTclass priority_queue{public:void push(const T val){_con.push_back(val);adjust_up(_con.size()-1);}void pop(){std::swap( _con[_con.size()-1],_con[0]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T top()const{assert(!_con.empty());return _con[0];}void swap(priority_queue con){if(_con!con._con)_con.swap(con._con);}private:void adjust_up(size_t child){Compare comfunc;size_t parent child;while(parent0){parent (child-1)/2;if(comfunc(_con[parent],_con[child])){std::swap(_con[parent],_con[child]);}child parent;}}void adjust_down(size_t parent){Compare comfunc;size_t child parent*21;while(child_con.size()){if(child1_con.size()comfunc(_con[child],_con[child1])){child;}if(comfunc(_con[parent],_con[child])){std::swap(_con[parent],_con[child]);}parent child;child parent*21;}}Container _con;};
