🏖️作者：@malloc不出对象
⛺专栏：C++的学习之路
👦个人简介：一名双非本科院校大二在读的科班编程菜鸟，努力编程只为赶上各位大佬的步伐🙈🙈
目录
- 前言
- 一、priority_queue的介绍
- 二、priority_queue的使用
- 三、仿函数
- 四、priority_queue的模拟实现
前言
本篇文章讲解的是优先级队列的使用以及模拟实现。
一、priority_queue的介绍
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
- 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素- 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
- 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
二、priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
| 函数声明 | 接口说明 |
|---|---|
| empty() | 检测优先级队列是否为空，是返回 true，否则返回 false |
| top() | 返回优先级队列中最大元素（最小元素），即堆顶元素 |
| push(x) | 在优先级队列中插入元素 x |
| pop() | 删除优先级队列中最大元素（最小元素），即堆顶元素 |
| size() | 返回优先级队列中元素的个数 |
下面我们来简单使用一下priority_queue：
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;void test()
{// 默认是大堆, 底层是按照小于来进行比较的priority_queue<int, vector<int>> pq1; pq1.push(1);pq1.push(3);pq1.push(0);pq1.push(7);pq1.push(2);while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;// 要想创建小堆，此时我们应该在三个模板参数显式传递greater仿函数，它的底层是按照大于来进行比较的，我们需要包含functional这个头文件才能使用priority_queue<int, vector<int>, greater<int>> pq2;pq2.push(1);pq2.push(3);pq2.push(0);pq2.push(7);pq2.push(2);while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;
}int main()
{test();return 0;
}
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。
#include <iostream>
#include <queue>
#include <functional>
using namespace std;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);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
private:int _year;int _month;int _day;
};
void TestPriorityQueue()
{// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;// 如果要创建小堆，需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));while (!q2.empty()){cout << q2.top() << " ";q2.pop();}cout << endl;
}int main()
{TestPriorityQueue();return 0;
}
优先级队列的使用成本很低，下面我们来做一道题吧：
LeetCode 215. 数组中的第K个最大元素
这题使用优先级队列可谓是非常的简单，题目要求第K大的数，我们直接利用优先级队列建立一个大堆，再pop掉前K-1个数，此时栈顶元素就是最大值也是第K大的数了。
首先建堆的时间复杂度为O(N)，然后调整建堆的时间复杂度为O(logN)循环K次，所以最终这种解决方案的时间复杂度为O(N + K * logN)，如果N很大时需要很大的空间，那么还没有更优的解法呢？
我们可以考虑只建一个K大小的小堆这样时间复杂度就为O(K)了，比起O(N)来说可以节省不少的空间，建一个K大小的小堆，遍历后N - K个元素，如果它大于栈顶元素就加入进来调整建堆，最后你会发现前K个大的数都在这个小堆中，而栈顶元素就为这K个元素当中最小的那个，也就是第K大的元素！！总的时间复杂度为O(K + (N - K) * logK).
三、仿函数
仿函数（Functor）是一种可以像函数一样被调用的对象，它是一个类或者结构体，它实现了函数调用运算符（operator()），可以像普通函数一样被调用。与函数不同，仿函数可以存储状态并且可以在多次调用之间保持其状态。
此外，仿函数可以通过模板参数进行参数化，以支持不同类型的参数和返回类型，使其更加灵活。
在C++中，仿函数通常被用于泛型编程中的算法函数中，这些算法函数可以接受仿函数作为参数，从而实现不同的算法行为。通过使用仿函数，我们可以在运行时动态地决定算法的行为，这种灵活性使得C++中的泛型编程更加强大。
#include <iostream>
using namespace std;template<class T>
struct Less
{bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:template<class T>bool operator()(const T& x, const T& y){return x > y;}
};int main()
{Less<int> lessFunc; // LessFunc对象就是一个仿函数，它可以像函数一样被调用cout << lessFunc(7, 2) << endl;cout << lessFunc.operator()(7, 2) << endl;cout << Less<int>()(2, 7) << endl; // 匿名对象调用operator()函数Greater<double> greaterFunc;cout << greaterFunc(2.0, 1.2) << endl;cout << greaterFunc.operator()(3.4, 4.6) << endl;cout << Greater<double>()(2.0, 1.2) << endl;return 0;
}
仿函数可以是类对象也可以是结构体对象，它也经常与我们的函数指针进行对比，我们的函数指针常用于回调函数之中，它并不是直接去调用那个函数，而是通过在一个函数中通过函数指针去间接那个函数，比起仿函数它还需要写函数参数以及返回值类型，这一点可能会给我们带来极大的困难，而我们的仿函数此时就显得非常好用了。
下面我们来看看这段代码，我们想实现的是日期类的优先级队列：
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
using namespace std;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);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;
};void TestPriorityQueue()
{// 大堆priority_queue<Date*> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 28));q1.push(new Date(2018, 10, 30));while (!q1.empty()){cout << *(q1.top()) << endl;q1.pop();}cout << endl;// 小堆priority_queue<Date*, vector<Date*>, greater<Date*>> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));while (!q2.empty()){cout << *(q2.top()) << endl;q2.pop();}cout << endl;
}int main()
{TestPriorityQueue();return 0;
}
我们来看看结果：
从上图我运行了三次，三次的结果都不同？？这是为何？？
这是因为库提供的仿函数不符合我们的要求，此时我们要比较的是日期类的值而非指针，就是我们比较的是指针，所以每次得出的结果都是不确定的，那么既然库中提供的仿函数不满足我们的需求，那我们就可以自行去实现一个。
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
using namespace std;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);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;
};struct PDateLess
{bool operator()(const Date* p1, const Date* p2){return *p1 < *p2; // 比较日期}
};struct PDateGreater
{bool operator()(const Date* p1, const Date* p2){return *p1 > *p2;}
};void TestPriorityQueue()
{// 大堆priority_queue<Date*, vector<Date*>, PDateLess> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 28));q1.push(new Date(2018, 10, 30));while (!q1.empty()){cout << *(q1.top()) << endl;q1.pop();}cout << endl;// 小堆priority_queue<Date*, vector<Date*>, PDateGreater> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));while (!q2.empty()){cout << *(q2.top()) << endl;q2.pop();}cout << endl;
}int main()
{TestPriorityQueue();return 0;
}
仿函数其实是C++中设计的非常好的一点，关于仿函数现阶段我们先就讲到这里，后续遇到了我们再来详谈。
四、priority_queue的模拟实现
// priority_queue.h
namespace curry
{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<int>, class Compare = less<T>>class priority_queue{public:priority_queue(){}template <class InputIterator> // 任意类型迭代器构造priority_queue(InputIterator first, InputIterator last): _con(first, last){int size = _con.size() - 1; for (int i = (size - 1) / 2; i >= 0; --i) // 注意: 这里一定要使用int！如果使用size_t的话假设只有一个元素，--i就变为了-1，如果是size_t的话，i将会是一个很大的数此时造成死循环ajustDown(i); //向下调整建堆}void ajustUp(int child){Compare com;int 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 ajustDown(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}// if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(int x){_con.push_back(x);ajustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();ajustDown(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}
本篇文章的讲解就到这里了，如果有任何错处或者疑问欢迎大家评论区交流哦~~ 🙈 🙈
