初识C++ · 优先级队列

目录

前言：

1 优先级队列的使用

2 优先级队列的实现

3 仿函数

---

前言：

栈和队列相对其他容器来说是比较简单的，在stl里面，有一种容器适配器是优先级队列（priority_queue），它也是个队列，但是不大像队列，本文中简略介绍如何使用和模拟实现它。

---

1 优先级队列的使用

要使用，先文档：

文档黑体第一句话就是，优先级队列是一种容器配置器，容器配置器是？电脑有电源适配器，起到提供电源的作用，但是这个适配器不是充电器，即充电的时候，电源来自于电线，但是我们不能直接拿电线充电吧？这时候适配器就有用了，通过封装，使得两边达到一个配合的效果，容器配置器同理。当然这不是重点。

模板是必要的，模板参数有3个，参考栈和队列，第二个参数是底层用的哪种容器进行实现的，这里的默认是使用的顺序表，第三个参数是仿函数，后面介绍。

那么在来看看成员函数：

很少是吧，可以说成员函数和队列没有什么差别，所以我们现在简单使用一下：

int main()
{priority_queue<int> q1;q1.push(2);q1.push(1);q1.push(4);q1.push(3);q1.push(5);cout << q1.size() << endl;while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;cout << q1.size() << endl;return 0;
}

使用很简单，但是打印的结果却，，有点奇怪？

这就是优先级队列的特殊之处了，我们并没有对它进行排序，但是打印出来是默认有序的，这是因为它的本质是堆，而模板参数第三个仿函数的参与，决定了它是大堆还是小堆，默认是升序的，可以理解为升序状态下谁最小谁优先级最高，所以先被打印。

但是实际上，不用管那么多，就把它认为是堆就ok了，所以我们实现的时候需要实现向上调整算法和向下调整算法。

对于仿函数我们放在实现了80%在介绍。

---

2 优先级队列的实现

我们需要实现以下几个接口：

empty,size,push,pop,top，接口不多，另外还要实现向上调整算法和向下调整算法。

优先级队列的一般结构为：

template <class T,class container = vector<T>>
class priority_queue
{
public:private:container _con;};

模板的第三个参数先不急。

简单的几个接口我们一股脑实现就完事了：

void push(const T& val)
{_con.push_back(val);adjust_up(_con.size() - 1);
}bool empty()
{return _con.empty();
}void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}size_t size()
{return _con.size();
}const T& top()
{return _con[0];
}

这部分是没什么难度的。

随机要实现的是push和pop，这里提问，为什么默认的底层实现是vector呢？

因为堆的本质，就是一块连续的空间，我们只是把它抽象为了完全二叉树。

push数据之后，堆本身的结构被破坏了，所以我们需要向上调整数据，在数据结构初级的时候，已经介绍过两种算法，这里过一下就Ok：

向上调整算法是通过孩子节点和父节点的值进行比较，然后交换位置，可能有点倒反天罡，谁的值大谁就当爸爸？我们知道孩子节点的下标之后，父节点的下标就是（孩子下标 - 1） / 2，如果不熟悉可以拿图推演一下，最后一次交换的时候，孩子节点的下标变成了父节点的下标，所以判断条件应该是孩子节点的下标是否合法，即是否大于0：

void adjust_up(size_t child)
{size_t parent = (child - 1) / 2;while (child > 0){if(_con[parent] < _con[child]){swap(_con[parent],_con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

此时push的的准备工作就做好了，插入，调整，完成：

void push(const T& val)
{_con.push_back(val);adjust_up(_con.size() - 1);
}

与之对应的是pop，pop对应的准备工作是向下调整算法，向下调整算法有几个需要注意的点就是，我们建大堆，那么就要在孩子节点中找到两个孩子中较大的那一个，除此之后，不是所有的节点都有两个子节点，所以我们需要保证孩子 + 1不小于size，这是基础工作，随机就是比较大小，谁大谁就往上：

void adjust_down(size_t parent)
{size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child++;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}

pop的准备工作也是完毕了，那么pop就行，对于堆部分有些遗忘的同学就会想为什么涉及到向下调整，因为删除，为了效率和不破坏堆的结构，我们的措施是首尾交换，向下调整。

void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}

---

3 仿函数

仿函数是本文的重点，我们需要先知道什么是仿函数？

先看一段这样的代码：

template <class T>
struct Less
{bool operator()(const T& a,const T& b){return a > b;}
};
void Func(int ,int)
{cout << endl;
}int main()
{Less<int> Fun;Fun(1,2);Func(1,2);return 0;
}

如果说只看主函数的代码，就会容易觉得，这不就是两个函数调用吗？仿函数仿函数，顾名思义，模仿函数，因为调用的时候挺像函数的，但是实际上，它是一个类，这个类实例化对象，使用重载后的()，我们称这个过程叫做仿函数调用，仿函数实际上只有一个东西，就是重载的()。

重载的()没有其他东西，只有比较，对于内置类型我们可以直接比较，对于自定义类型我们可能要重载一下> 或者 <。

所以，仿函数是个类，类里面的函数是重载的()，一般是两个参数，用于比较使用。

所以我们在向上调整算法和向下调整算法的实现里面的比较，就可以用仿函数完成，进而控制升序降序，那么我们就还要写两个类：

//仿函数
template <class T>
struct less
{bool operator()(const T& x,const T& y){return x < y;}
};template <class T>
struct greater
{bool operator()(const T& x, const T& y){return x > y;}
};

那么对应更新的，就是我们的两个算法：

template <class T,class container = vector<T>,class compare = greater<T>>void adjust_up(size_t child)
{compare com;size_t parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if(com(_con[parent] , _con[child])){swap(_con[parent],_con[child]);child = parent;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 (_con[child] > _con[parent])if(com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

向下调整算法这里有个注意的，if(child + 1 < _con.size() && com(_con[child], _con[child + 1]))，第一个判断条件放在前面是最好的，因为越界了不用了比较了，代码逻辑更严密。

但是这里使用了仿函数好像也没有什么特别的，无非就是用了一个像函数调用一样的类而已，为什么不用C语言中qsort里面的函数指针呢？

在C++里面函数指针并不常用，难写不说，代码的可移植性还不高，目前我们针对的内置类型使用的仿函数效果不明显，我们引入一个日期类，一个自定义类型，进行日期的比较。

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}
private:size_t _year;size_t _month;size_t _day;
};

对于自定义类型的比较重载已经写在了类里面，现在直接比较就可以了：

class DateGreater
{bool operator()(const Date& d1, const Date& d2){return d1 > d2;}
};
class DateLess
{bool operator()(const Date& d1, const Date& d2){return d1 < d2;}
};

void Test2_priority_queue()
{priority_queue<Date> q1;q1.push({ 2024, 4, 17 });q1.push({ 2024, 4, 18 });q1.push({ 2024, 4, 19 });q1.push({ 2024, 4, 20 });cout << q1.size() << endl;while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;
}

对比淘宝，淘宝的的排序，比如综合评分排序，销量排序等，用户点击对应按钮，系统就会调用对应的函数，使用的就是仿函数，函数指针在C++里面不太常用，它的类型和变量名混杂一起，看起来不太舒服。

仿函数的一般使用差不多了，但是如果我们给优先级队列里面存放日期类的指针，但是相比较日期类的大小怎么办呢？

void Test3_priority_queue()
{priority_queue<Date*, vector<Date*>> q1;q1.push(new Date(2024,5,20));q1.push(new Date(2024,5,21));q1.push(new Date(2024,5,22));q1.push(new Date(2024,5,23));while (!q1.empty()){cout << *(q1.top()) << " ";q1.pop();}cout << endl;
}

比如这样，里面都是指针，我们push的也是new出来的指针，我们使用的仿函数是：

class DateGreater
{bool operator()(const Date& d1, const Date& d2){return d1 > d2;}
};
class DateLess
{bool operator()(const Date& d1, const Date& d2){return d1 < d2;}
};

那么这个仿函数就不可以了，比较出来的都是随机结果，这是因为new出来的地址都是随机的，而默认的是比较的指针，打印出来的是对应的日期，所以结果一会儿是对的一会儿是错的，这是因为仿函数的错误使用，我们应该解引用之后再进行比较，这里就要另外提供一个仿函数了：

class PDateGreater
{
public:bool operator()(Date* d1, Date* d2){return *d1 > *d2;}	
};

光提供了还不行，我们还要显式调用：

void Test3_priority_queue()
{priority_queue<Date*, vector<Date*>,PDateGreater> q1;q1.push(new Date(2024,5,20));q1.push(new Date(2024,5,21));q1.push(new Date(2024,5,22));q1.push(new Date(2024,5,23));while (!q1.empty()){cout << *(q1.top()) << " ";q1.pop();}cout << endl;
}

这样就是完美的了。仿函数的简单介绍就到这里。

---

感谢阅读！