智通人才网_上海网站制作计划_如何营销推广_典型十大优秀网络营销案例

我们今天又见面啦，给生活加点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;//成员变量
};

插入数据

首先，在