文章目录
- priority_queue的模拟实现
- 优先级队列
- 优先级队列的模拟实现(默认创建大堆)
- 结构定义和构造函数
- 插入数据
- 删除数据
- 简单接口
- 仿函数
- 结语
我们今天又见面啦,给生活加点impetus!!开启今天的编程之路!!
今天我们进入优先级队列,复习数据结构-堆,进入仿函数,运用仿函数
作者:٩( ‘ω’ )و260
我的专栏:C++初阶,数据结构初阶,题海探骊,c语言
欢迎点赞,关注!!
priority_queue的模拟实现
优先级队列
在 C++ 里,优先级队列(Priority Queue)是一种特殊的队列,它的元素按照优先级排序,优先级高的元素会先被处理。C++ 标准库 头文件提供了 std::priority_queue 容器适配器来实现优先级队列的功能。
优先级:数值大的默认的是优先级更高
敏锐的话,其实能够发现其实能够明白优先级队列的底层是什么,是堆的结构,我们可以写代码验证一下:
priority_queue<int> pq;pq.push(5);pq.push(1);pq.push(5);pq.push(6);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
结果是6 5 5 2 1。
其实就是大堆按照升序排列。如果我们想要实现降序,需要添加greater 仿函数,这里的greater已经是库中定义好的类。
为什么呢?
因为这里其实有三个参数,第一个参数是数据类型,第二个是优先级队列的参数是底层容器,第三个参数是控制大小排序的,为什么这里我们没有传递呢?因为这里控制大小排序的函数给了缺省值,底层容器也给了缺省值。
成功实现降序。
priority_queue 默认是一个大顶堆,也就是优先级高(数值大)的元素排在前面
优先级队列的模拟实现(默认创建大堆)
接下来我们直接来进行模拟实现:
因为是堆的结构,代码跟堆及其相似,我们这里需要学会仿函数的使用。
结构定义和构造函数
因为优先级队列的底层是基于堆,堆的底层是什么呢?是vector,所以我们第二个模版参数选择传递vector。
本质的原因是:在堆中需要涉及大量的下标访问,在vector中底层数组是支持下标访问的,当然,deque也是可以作为传递的容器的,但是效率没有vector的效率好
来看代码:
template<class T,class Container=vector<T>>
class priority_queue{priority_queue()//构造函数{}
private:Container _con;//成员变量
};
插入数据
首先,在