网站建设方案和报价,网站建设网络宣传,php制作招聘网站,百度标记号码认证平台C --- priority_queue前言一、priority_queue的使用二、priority_queue的简单实现1.整体结构2.主要方法pushpoptopemptysize三、构造迭代器区间构造默认构造四、仿函数前言
priority_queue是C容器之一#xff0c;意为优先级队列#xff0c;虽说叫做队列#xff0c;但是其底…
C --- priority_queue前言一、priority_queue的使用二、priority_queue的简单实现1.整体结构2.主要方法pushpoptopemptysize三、构造迭代器区间构造默认构造四、仿函数前言
priority_queue是C容器之一意为优先级队列虽说叫做队列但是其底层结构是堆唯一和队列有关是使用此容器时包含的标准头文件是queue通过此容器的学习会学习到一个新的知识仿函数。
一、priority_queue的使用
priority_queue的接口和stack与queue的基本一样主要是pushpoptopemptysize这些接口只是底层的结构不同。
需要注意的是底层默认创建大堆结构需要变成创建小堆结构这里需要使用新的知识仿函数仿函数的详细介绍留在简单实现板块还有同样因为数据有特殊的顺序所以底层不支持迭代器遍历。
// 在这里仿函数是第三个模板参数控制的是创建堆的结构
// greater --- 更大的
// less --- 更小的
// 不过标准库里的是less控制大堆greater控制小堆是反过来的这一点需要注意一下
// 标准库提供的接口和前面的stackqueue相似主要就是pushpoptopsizeempty这几个
// 使用起来也是差不多的同样因为数据有特殊的顺序所以底层不支持迭代器遍历
// 尽管堆的底层是数组但是底层没有实[]的重载。// 创建一个堆的对象
//priority_queueint hp;
priority_queueint, vectorint, greaterint hp;hp.push(4);
hp.push(2);
hp.push(6);
hp.push(7);
hp.push(1);
hp.push(8);// 循环取堆顶元素打印
while (!hp.empty())
{cout hp.top() ;hp.pop();
}
cout endl;打印结果 此时仿函数是greater创建的是小堆循环取堆顶元素则是升序排列。
二、priority_queue的简单实现
1.整体结构
priority_queue的底层是一个堆结构并且堆结构是由数组实现的完全二叉树所以这里直接使用容器适配器默认适配vector来作为priority_queue的结构。
templateclass T, class Container vectorT
class priority_queue
{
public://………………// 各种方法
private:Container _con;
};2.主要方法
priority_queue的主要接口就是pushpoptopemptysize。
push
由于堆结构本身就有性质要么是大堆要么就是小堆所以这里在堆尾插入完数据后需要调整数据的位置以满足堆的结构。
// 在堆尾入数据
void push(const T x)
{// 插入数据_con.push_back(x);// 向上调整算法Adjust_up(size() - 1);}// 向上调整算法
void Adjust_up(size_t child)
{// 已知孩子节点求双亲节点size_t parent (child - 1) / 2;// 最坏的情况child调整至根节点才结束while (child 0){// 大堆谁大谁向上调整// 小堆谁小谁向上调整if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}在向上调整算法中参数接收的是孩子节点的下标根据二叉树的性质可知双亲节点的下标 孩子节点 - 1/ 2求出双亲节点的下标后比较它们两个的大小孩子节点大大堆/ 小小堆于双亲节点则进行交换随后更新child和parent的位置指向下一棵子树若插入后满足所需要的堆结构则直接跳出循环最坏的情况下child调整至根节点才结束所以这里的循环结束条件是child 0。
pop
由于堆底层是数组并且堆的pop操作是在堆顶进行的所以相当于进行头删操作这样效率较低首先先将堆顶数据和堆尾数据进行交换这样一来需要删除的数据就在堆尾而数组删除最后一个数据效率很高直接将其删除掉即可然后调整堆结构即可这里使用向下调整算法。
// 在堆顶出数据
void pop()
{// 删除堆顶元素先将堆顶和堆尾元素交换再删除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 向下调整算法Adjust_down(0);
}// 向下调整算法
void Adjust_down(size_t parent)
{// 已知双亲节点求左孩子节点右孩子节点即左孩子 1size_t child parent * 2 1;// 最坏的情况是根节点调整到叶子节点while (child size()){// 首先右孩子得存在合法// 如果右孩子大于/小于左孩子则child走到大/小的一方if (child1 size() _con[child 1] _con[child]){child;}// 大堆谁大谁向上调整// 小堆谁小谁向上调整if (_con[child] _con[parent]){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}
}在向下调整算法中参数接收的是根节点的下标根据二叉树的性质可知左孩子节点 双亲节点 * 2 1右孩子则是左孩子 1在此算法中额外多出一步是比较左右孩子的大小关系当堆结构为大堆时child走到大的那一个孩子处同理当堆结构为小堆时child走到小的那一个孩子处这一步要注意右孩子的下标需要存在合法之后就和向上调整算法里的一样孩子节点和双亲结点比较谁大 / 小 就进行交换随后更新child和parent的位置走到下一棵子树的位置继续进行调整若满足所需要的堆结构则直接跳出循环最坏的情况是根节点调整到叶子节点才结束所以这里的循环结束条件是child 堆的szie。
top
此接口和下面的两个接口都直接使用适配即可。
// 取堆顶元素
const T top() const
{return _con[0];
}empty
// 判空
bool empty()
{return _con.empty();
}size
// 取有效元素个数
size_t size()
{return _con.size();
}三、构造
迭代器区间构造
priority_queue支持迭代器区间构造并且底层实现的是函数模板形式所以我们也去实现函数模板形式。
// 迭代器区间构造
templateclass InputIterator
priority_queue(InputIterator first, InputIterator last)// 先将此迭代器区间入堆 --- _con是容器支持直接迭代器区间构造:_con(first,last)
{// 然后就是向下调整建堆 --- 因为此时还不是堆结构for (size_t i (size() - 1 - 1) / 2; i 0; i--){Adjust_down(i);}
}这里初始化列表里直接复用适配器的迭代器区间构造即可然后虽入了数据但是此时不是一个堆结构同样需要进行调整这里采用的是向下调整算法至于为什么不使用向上调整算法因为向上调整算法的时间复杂度高于向下调整算法时间复杂度详情请回顾我的数据结构 — 堆 的这篇博客link
在向下调整建堆中由于是向下调整双亲节点和孩子节点进行比较向下调整所以这里的for循环的循环变量 i 也就是双亲节点的下标并且二叉树的最后一层节点是叶子节点所以双亲节点的最后一层是倒数第二层size() - 1 是最后一个位置的下标不能保证此位置上有节点此位置是右孩子再减一就是左孩子的下标已知孩子求双亲就是(size() - 1 - 1) / 2直至调整至根节点所以循环结束条件就是i 0。
默认构造
由于我们自己写了一种构造编译器就不再生成默认构造了而默认构造能满足我们的需求所以这里强制让编译器生成默认构造。
// 由于我们自己写了一种构造编译器就不生成默认构造了
// 所以这里强制让编译器生成
priority_queue() default;四、仿函数
所谓仿函数也叫做函数对象它其实是一个类其中重载了运算符operator()使得这个类能够像函数一样被调用。 回到堆的代码中在向上或者向下调整算法里面我们控制大堆小堆结构是通过孩子和双亲大小关系来确定的但是这个关系是固定死的要么大于要么小于这里就可以使用仿函数不用写死关系通过调用仿函数创建的对象去调用运算符()在此重载内部再去确定比较关系即可。
// 这个就是仿函数 / 函数对象
// 仿函数代替的就是C语言的函数指针
// 简单来说就是一个类通过这个类类型创建的对象去模拟函数那样被调用
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;}
};// 使用仿函数控制大小比较关系
// 需要多增加一个模板参数
templateclass T, class Container vectorT,class Compare lessT
class priority_queue回到向上调整算法中在方法内部通过Compare创建了一个对象com在孩子和双亲比较的逻辑里替换了之前的固定写死一方的大小关系变成通过com对象去调用运算符()这样就看起来像是调用了函数这就是仿函数。
// 向上调整算法
void Adjust_up(size_t child)
{Compare com;size_t parent (child - 1) / 2;while (child 0){//if (_con[child] _con[parent])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}
}调用关系如下图所示 这里的参数x接收的就是parent参数y接收的就是child。 同理向下调整算法里parent和child的比较逻辑child和child1的比较逻辑也是如此替换。 需要注意的是对于类模板而言使用仿函数时这里传递的是类型而对函数模板而言使用仿函数时传递的则是对象。
