网站内容运营方案,巨省网站,设计的软件都有什么,网站建设可行性分析目录 一#xff1a;#x1f525;介绍二#xff1a;#x1f525;priority_queue 的基本操作三#xff1a;#x1f525;priority_queue 的原型定义四#xff1a;#x1f525;重写仿函数4.1.仿函数的介绍4.2.priority_queue仿函数代码示例 五#xff1a;#x1f525;pri… 目录 一介绍二priority_queue 的基本操作三priority_queue 的原型定义四重写仿函数4.1.仿函数的介绍4.2.priority_queue仿函数代码示例 五priority_queue模拟底层实现堆排序总结 一介绍 普通的队列是一种先进先出的数据结构元素在队列尾追加而从队列头删除。 在优先队列中元素被赋予优先级。当访问元素时具有最高优先级的元素最先删除。优先队列具有最高级先出 first in, largest out的行为特征。 优先队列具有队列的所有特性包括队列的基本操作只是在这基础上添加了内部的一个排序它本质是一个堆实现的。
二priority_queue 的基本操作
首先使用priority_queue时需包含头文件
#include priority_queue
): 和队列基本操作相同
名字描述top访问队头元素empty队列是否为空size返回队列内元素个数push插入元素到队尾 (并排序)emplace原地构造一个元素并插入队列pop弹出队头元素swap交换内容
三priority_queue 的原型定义
template class T, class Container vectorT, class Compare lesstypename Container::value_type
class priority_queue模板申明带3个参数其中 T 为数据类型Container 为保存数据的容器适配器Compare 为元素比较方式。Container必须是用数组实现的容器比如 vector,deque 等等但不能用 list。STL里面默认用的是vector。比较方式默认用operator所以如果把后面2个参数缺省的话优先队列就是大顶堆降序队头元素最大。
greater和less是std实现的两个仿函数
类的对象可以像函数一样使用其实现就是类中实现一个operator()
这个类的对象就有了类似函数的行为就是一个仿函数类了//降序队列(默认大根堆) 把后面2个参数缺省
priority_queue int q;//升序队列(小根堆)
priority_queue int,vectorint,greaterint q;
四重写仿函数
4.1.仿函数的介绍 仿函数Functor又称为函数对象Function Object是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样不过作为仿函数的类都必须重载 operator() 运算符。因为调用仿函数实际上就是通过类对象调用重载后的 operator() 运算符。 仿函数的优点 写一个简单类除了维护类的基本成员函数外只需要重载 operator() 运算符 。这样既可以免去对一些公共变量的维护也可以使重复使用的代码独立出来以便下次复用。而且相对于函数更优秀的性质仿函数还可以进行依赖、组合与继承等这样有利于资源的管理。 简言之就是一个类可以定义一些变量省的使用全局变量造成命名空间污染
4.2.priority_queue仿函数代码示例
//仿函数 可以像操作函数一样操作对象 因为重载了() 不是什么新语法
templateclass T
class less
{
public:bool operator()(const T a, const T b){return a b;}
};templateclass T
class greater
{
public:bool operator()(const T x, const T y){return x y;}
};五priority_queue模拟底层实现堆排序
templateclass T
class less
{
public:bool operator()(const T a, const T b){return a b;}
};templateclass T
class greater
{
public:bool operator()(const T x, const T y){return x y;}
};templateclass T, class Container std::vectorT, class Compare lessT
class priority_queue
{
public:priority_queue() default; // 强制生成默认构造函数template class 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_down(size_t parent){Compare comfunc;size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() comfunc(_con[child], _con[child 1])){child;}if (comfunc(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else break;}}//向上调整算法void adjust_up(size_t child){Compare comfunc;int parent (child - 1) / 2;while (child 0){if (comfunc(_con[parent], _con[child])) std::swap(_con[parent], _con[child]);else break;child parent;parent (child - 1) / 2;}}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}private:Container _con;Compare comp;
};总结
优先队列到此就作了个小结。如果有任何疑问都可以私信我希望我们共同进步 有错误还请在评论区指正学无止境。
