C++——优先级队列

很楠不爱 2024-06-12 13:35:01 阅读 86

前言：这篇文章我们继续来分享一个c++的容器——优先级队列。

一.理解优先级

何为优先级一说？实际上就是有顺序的意思。

优先级队列，即有顺序的队列，是一个无需我们自己进行排序操作，在数据传入时就会由容器自己排好序的队列。

先来看实例：

使用该队列，同样需要包含头文件#include<queue>。

在默认情况下，优先级队列是按照从大到小排序的，而在数据结构中，也有一个能够自主排序，没错，就是堆。从大到小的顺序，也就是大堆。

那么如果想要实现小堆，又该怎么办呢？只需要增加一下模版参数：

至于为什么这样写就是小堆，我们再接下来的模拟实现中进行解答。

二.基本框架

堆可以通过父节点或字节点的下标来互相找到对方的下标，所以一般情况都以数组为模板。

template <class T,class Container = vector<T>>class priority_queue{public://向上调整void adjust_up(size_t child){int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;int parent = (child - 1) / 2;}else{break;}}}//向下调整void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.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;}}}//插入void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}//删除void pop(){swap(_con[_con.size() - 1], _con[0]);_con.pop_back();adjust_down(0);}//队头元素T& top(){return _con[0];}//数据个数size_t size(){return _con.size();}//判空bool empty(){return _con.empty();}private:Container _con;};

这里我们直接给出优先级队列的基本常规操作，本质就是堆的各种操作，不再一一分享。

而我们要重点分享的，就是如何切换升降序。

三.仿函数

从名字就能看出，这是一个可以冒充函数的家伙，先来看例子：

template <class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};

这段代码不难理解，在一个类中声明了一个运算符重载函数，这个函数能够进行大小比较。

再来看这段代码，能够发现我们能够直接通过一个对象来进行两个数据之间的比较。

这就是所谓的仿函数。

上述仿函数是进行“小于”比较，同样我们也可以在创造一个仿函数来进行“大于”比较。

如此一来，我们便可以通过类模板将这两个仿函数用于排序比较。

四.实现可选优先级

直接看代码：

//小于比较template <class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};//大于比较template <class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};template <class T,class Container = vector<T>,class compare = less<T>>//注意class priority_queue{//大堆public://向上调整void adjust_up(size_t child){compare com;//注意int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child]))//注意{swap(_con[child], _con[parent]);child = parent;int parent = (child - 1) / 2;}else{break;}}}//向下调整void adjust_down(size_t parent){compare com;//注意size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))//注意{++child;}if (com(_con[parent], _con[child]))//注意{swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}

其中less为小于比较的类，而greater为大于比较的类。

而后我们通过使用类模板参数compare将两者整合在一起，因为库里的优先级队列默认即为大堆，所以我们使用缺省参数默认为less。

前边已经提到，使用仿函数，就是使用对应类的对象，所以我们需要创建compare类的对象com，并传入比较内容进行比较。

这里要注意两个比较数据的先后位置，要按照到底是谁大于谁而传入正确的先后顺序。