68Design一样设计网站,福鼎网站建设培训,企业老板培训课程,深圳设计工作室有哪些STL之优先级队列#xff08;堆#xff09;的模拟实现与仿函数 文章目录 STL之优先级队列#xff08;堆#xff09;的模拟实现与仿函数优先级队列的概念priority_queue的接口介绍优先级队列的构造函数 priority_queue模拟实现类成员构造函数向下调整算法——正常实现 push向…STL之优先级队列堆的模拟实现与仿函数 文章目录 STL之优先级队列堆的模拟实现与仿函数优先级队列的概念priority_queue的接口介绍优先级队列的构造函数 priority_queue模拟实现类成员构造函数向下调整算法——正常实现 push向上调整——正常实现 pop 仿函数/函数对象仿函数的概念仿函数的作用 使用仿函数来实现优先级队列的逻辑判断新增模板参数使用仿函数实现泛型的向下调整算法与向上调整算法 优先级队列模拟——最终版代码仿函数的应用STL中实现的比较STL中的建堆算法 优先级队列的概念 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。 本质就是一个堆 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。 . 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作 list不支持随机访问所以不能当做其标准容器类 priority_queue的接口介绍 pop删除堆顶的数据 top取出堆顶的数据 push向堆插入数据 size返回堆里面的元素个数 empty判断堆是否为空 swap交换两个堆 优先级队列的构造函数 可以使用迭代器进行初始化 但是这个迭代器是一个随机迭代器 //简单使用
#pragma once
#include queue
#includeiostream
#include functional//less和greater的头文件
using namespace std;
int main()
{//大堆priority_queue int pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;//小堆priority_queue int,vectorint,greaterint pq1;pq1.push(3);pq1.push(1);pq1.push(2);pq1.push(5);while (!pq1.empty()){cout pq1.top() ;pq1.pop();}cout endl;return 0;
} priority_queue模拟实现 容器适配器是不需要迭代器的如果有了迭代器是不能保证最大/最小的先出 类成员 namespace MySTL
{templateclass T,class Container std::vectorTclass priority_queue{private:Container _con;};
}构造函数
namespace MySTL
{templateclass T,class Container std::vectorTclass priority_queue{public:priority_queue(){}templateclass InputIteratorpriority_queue(InputIterator first,InputIterator last):_con(first,last)//直接调用vector的构造{//此时还不是堆//向下调整建堆for (int i (_con.size() - 2) / 2; i 0; i){adjust_down(i);}}private:Container _con;};
}
向下调整算法——正常实现
namespace MySTL
{templateclass T,class Container std::vectorTclass priority_queue{private: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])//建大堆{std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;//没有更大的了退出}}}private:Container _con;};
} 向下调整算法的核心将父节点和自己的两个子节点对比找到其中一个最大大堆的或者最小小堆的子节点然后比较如果是建大堆若父节点比子节点还要小那么交换如果是建小堆若父节点比子节点还要大那么交换直到父节点比最大子节点还要大大堆或者是比最小的子节点还要小小堆则跳出循环或者直接调整到最后一个节点 push namespace MySTL
{templateclass T,class Container std::vectorTclass priority_queue{public:void push(const T value){//插入后要保持堆的结构//要进行向上调整_con.push_back(value);adjust_up(_con.size()-1);}private:Container _con;};
} 向上调整——正常实现
namespace MySTL
{templateclass T,class Container std::vectorTclass priority_queue{private: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;}}}private:Container _con;};
}
//这里如果使用parent0那么因为子节点还在下一个位置则无法调整根节点
//如果是parent0 因为parent 0-1/2 仍然为0则就会出现死循环向上调整就是将现在子节点和父节点对比一下然后如果是建大堆若子节点大于父节点那么进行交换 如果是建小堆若子节点小于父节点那么也交换 结束条件直到根节点是孩子或者建大堆的时候孩子比父亲小建小堆的时候孩子比父亲大 向上调整算最好使用孩子作为循环借宿的条件 pop namespace MySTL
{templateclass T,class Container std::vectorTclass priority_queue{public:void pop(){//交换std::swap(_con[0], _con[_con.size()-1]);//删除最后一个元素_con.pop_back();//向下调整算法adjust_down(0);}private: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])//建大堆{std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;//没有更大的了退出}}}private:Container _con;};
} int main()
{MySTL::priority_queue int pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;return 0;
} 仿函数/函数对象
仿函数的概念 首先仿函数究竟是什么呢——是一个类仿函数的类型对象我们叫做函数对象 templateclass T
struct less
{bool operator()(const T x,const T y){return x y;}
};
templateclass T
struct greater
{bool operator()(const T x,const T y){return x y;}
};仿函数的要求是要重载()()这也是一个运算符例如像是我们去调用pq1.pop()的函数后面的()就是一个函数调用符 int main()
{lessint lessFunc;lessFunc(0, 1);return 0;
}如果不看上面的类的定义单看后面的lessFunc(0,1)这就是一个函数调用函数名是lessFunc——但是现在实际上是一个类这就是为什么这个叫做仿函数这个对象叫做函数对象指的就是这个对象能像函数一样被使用 但是这个其实也是一个函数调用 lessFunc(0, 1);//将这个转换为一个运算符重载
lessFunc.operator()(0, 1);//等价于上面上面的仿函数的作用 那么仿函数究竟有什么作用呢看起来和一般的函数区别而且还多了一个封装看起来更加的麻烦了 我们可以举一个例子来看 //这是C语言的一个冒泡排序
void BubbleSort(int* a, int size,bool(*cmp)(int,int))
{for (int i 0; i size; i){int exchange 0;for(int j 1.;jsize-i;j){if (cmp(a[j-1],a[j])){std::swap(a[j - 1], a[j]);exchange 1;}}if (!exchange){break;}}
} 我们可以 看到在C语言中如果我们想要解决升序降序的问题我们就要传一个函数指针过来——如果不用函数指针那么我们就只能重新写一个函数了 那么在C中的类里面我们是否也可以传一个函数指针呢可以但是这样子不好看C的设计都是在尽量的不去使用指针 所以仿函数这时候就派上用场了 template class T,class Compare
void BubbleSort(T* a, int size,Compare com)//因为Compare其实是一个类所以要显示实例化而不是模板函数一样是推演实例化所以要多加一个参数
{for (int i 0; i size; i){int exchange 0;for(int j 1.;jsize-i;j){//if (a[j] a[j - 1])if (com(a[j], a[j - 1])){std::swap(a[j - 1], a[j]);exchange 1;}}if (!exchange){break;}}
}int main()
{lessint lessFunc;int a[] { 1,5,7,8,94,24,5,3,56,7 ,90 };BubbleSort(a, sizeof(a) / sizeof(a[0]), lessFunc);//升序排序//BubbleSort(a, sizeof(a) / sizeof(a[0]), lessint());//怎么写也是可以的因为是一个匿名对象如果这个函数对象是要使用一次的话可以直接使用匿名对象for (auto e : a){std::cout e ;}std::cout std::endl;greaterint greaterFunc;int b[] { 1,5,7,8,94,24,5,3,56,7 ,90 };BubbleSort(b, sizeof(b) / sizeof(b[0]), greaterFunc);//降序排序//BubbleSort(b, sizeof(b) / sizeof(b[0]), greaterint());for (auto e : b){std::cout e ;}return 0;
} less和greater就是我们刚刚写的仿函数 从我们实现代码的角度来说这是一个泛型是一个逻辑泛型——即com是一个逻辑如果需要升序就传一个lessFunc如果要降序就传一个greaterFunc 类型泛型就是不限类型逻辑泛型就是不限逻辑 仿函数一般都是传值因为仿函数的拷贝代价很小仿函数里面没有成员变量所以只有一个字节作为标记位 但是如果想要传引用也行 void BubbleSort(T* a, int size,const Compare com)//也是可以传引用的但是要加上const否则就无法接收匿名对象因为匿名对象具有常性
{for (int i 0; i size; i){int exchange 0;for(int j 1.;jsize-i;j){//if (a[j] a[j - 1])if (com(a[j], a[j - 1]))//因为是const对象调用所以仿函数内部都要加上const{std::swap(a[j - 1], a[j]);exchange 1;}}if (!exchange){break;}}
}templateclass T
struct less
{bool operator()(const T x,const T y)const//加上const让const对象能够调用{return x y;}
};
templateclass T
struct greater
{bool operator()(const T x,const T y)const{return x y;}
};我们也可以看到传引用其实很麻烦所以没有什么必要 使用仿函数来实现优先级队列的逻辑判断 我们上面的优先级队列要么只能是大堆要么只能是小堆不够泛用原因就是因为我们的逻辑是写死的但是学会了仿函数之后我们也可以实现逻辑泛型了 新增模板参数 templateclass T, class Container std::vectorT,class Compare lessT class priority_queue{public:// functionsprivate:Container _con;};
} 加上第三个模板参数仿函数 使用仿函数实现泛型的向下调整算法与向上调整算法 namespace MySTL
{templateclass Tstruct less{bool operator()(const T x, const T y){return x y;}};templateclass Tstruct greater{bool operator()(const T x, const T y){return x y;}};templateclass T, class Container std::vectorT,class Compare lessTclass priority_queue{public://functionsprivate:void adjust_up(size_t child){size_t parent (child - 1) / 2;Compare com;while (child 0){//if (_con[child] _con[parent])//建大堆//if (_con[parent] _con[child])//建大堆if(com(_con[parent], _con[child]))//我们要与库保持一致要小于实现大堆那么就要parent在前就是与上面的逻辑一样{std::swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child parent*2 1;Compare com;while (child _con.size()){//if (child 1 _con.size() _con[child] _con[child 1]))if (child 1 _con.size() com(_con[child], _con[child 1])))//我们要与库保持一致要小于实现大堆那么就要child在前child;//if (_con[parent] _con[child])//建大堆if(com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;//没有更大的了退出}}}private:Container _con;};
}测试用例 int main()
{//大堆MySTL::priority_queue int pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;//小堆MySTL::priority_queue int, vectorint, greaterint pq1;pq1.push(3);pq1.push(1);pq1.push(2);pq1.push(5);while (!pq1.empty()){cout pq1.top() ;pq1.pop();}cout endl;return 0;
}优先级队列模拟——最终版代码
namespace MySTL
{templateclass Tstruct less{bool operator()(const T x, const T y){return x y;}};templateclass Tstruct greater{bool operator()(const T x, const T y){return x y;}};templateclass T, class Container std::vectorT,class Compare lessTclass priority_queue{public:priority_queue()//无参构造{}templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last):_con(first, last)//直接调用vector的构造{//此时还不是堆//向下调整建堆for (int i (_con.size() - 2) / 2; i 0; i){adjust_down(i);}}void push(const T value){_con.push_back(value);adjust_up(_con.size()-1);}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:void adjust_up(size_t child){size_t parent (child - 1) / 2;Compare com;while (child 0){//if (_con[child] _con[parent])//建大堆//if (_con[parent] _con[child])//建大堆if(com(_con[parent], _con[child]))//我们要与库保持一致要小于实现大堆那么就要parent在前{std::swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child parent*2 1;Compare com;while (child _con.size()){//if (child 1 _con.size() _con[child] _con[child 1])if (child 1 _con.size() com(_con[child], _con[child 1]))//我们要与库保持一致要小于实现大堆那么就要child在前child;//if (_con[parent] _con[child])//建大堆if(com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;//没有更大的了退出}}}private:Container _con;};
}
仿函数的应用 要知道我们优先级队列的类型可以不只是库里面的类型还可以是自定义类型 class Date
{
public:Date(int year 1900, int month 1, int day 1): _year(year), _month(month), _day(day){}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}friend ostream operator(ostream _cout, const Date d){_cout d._year - d._month - d._day;return _cout;}private:int _year;int _month;int _day;
};如果一个自定义类型是支持比较大小的那么仿函数greater和less都是可以使用的里面的与 本质也是调用的是Date类的运算符重载 void testpriorityqueue()
{priority_queueDate q1;//默认是大堆q1.push(Date(2010, 1, 1));q1.push(Date(2010, 1, 2));q1.push(Date(2010, 1, 3));cout q1.top() endl;priority_queueDate,vectorDate,greaterDate q2;//默认是大堆q2.push(Date(2010, 1, 1));q2.push(Date(2010, 1, 2));q2.push(Date(2010, 1, 3));cout q2.top() endl;}
int main()
{testpriorityqueue();return 0;
} 现在如果我们传入的是这个自定义类型的指针呢 void testpriorityqueue()
{//大堆priority_queueDate* q3;q3.push(new Date(2010, 1, 1));q3.push(new Date(2010, 1, 2));q3.push(new Date(2010, 1, 3)); cout *q3.top() endl;//小堆priority_queueDate*,vectorDate*,greaterDate* q4;/q4.push(new Date(2010, 1, 1));q4.push(new Date(2010, 1, 2));q4.push(new Date(2010, 1, 3));cout *q4.top() endl;
}
int main()
{testpriorityqueue();return 0;
}我们发现这时候堆的比较好像就失效了!这是为什么呢因为我们传过去的是date类的地址此时我们传入的仿函数是用地址的大小去比较的谁地址谁大谁地址小谁小 因为每次地址是随机的所以每次的结果都会在改变 那么现在的结果已经不符合我们预期了怎么办 我们就可以重新写一个关Date* 的仿函数 struct PDateCompare_greater
{bool operator()(const Date* x,const Date* y){return *x *y;}
};
struct PDateCompare_less
{bool operator()(const Date* x,const Date* y){return *x *y;}
};
void testpriorityqueue()
{//大堆//priority_queueDate* q3;priority_queueDate*,vectorDate*,PDateCompare_less q3;q3.push(new Date(2010, 1, 1));q3.push(new Date(2010, 1, 2));q3.push(new Date(2010, 1, 3)); cout *q3.top() endl;//小堆priority_queueDate*,vectorDate*,PDateCompare_greater q4;q4.push(new Date(2010, 1, 1));q4.push(new Date(2010, 1, 2));q4.push(new Date(2010, 1, 3));cout *q4.top() endl;
}
int main()
{testpriorityqueue();return 0;
}如果比较的方式不是我们想要的那么我们就可以通过自己写一个仿函数来完成甚至如果自定义类不支持 与 重载我们也可以写一个仿函数来完成大小的比较 STL中实现的比较 STL中的建堆算法 STL中的建堆算法是在algorithm这个头文件中 push_heap将一个元素插入堆中pop_heap将一个元素从堆中移除make_heap 从一个范围内的元素中创建一个堆sort_heap 堆排序if_heap 判定一个范围内的元素是不是堆is_heap_until 找到第一个不按堆规则的元素
