C++优先队列详解与仿函数应用-开发者社区

基本特性

头文件：#include <queue>
命名空间：std
底层实现：通常基于堆（heap）数据结构实现
默认行为：大顶堆（最大元素优先出队）
时间复杂度：
- 插入元素：O(log n)
- 删除顶部：O(log n)
- 访问顶部：O(1)

1.2 快速上手优先级队列：常用操作详解

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

函数声明	接口说明
priority_queue()/priority_queue(first, last)	构造一个空的优先级队列（注意：priority_queue支持迭代器区间构造）
empty( )	检测优先级队列是否为空，是返回true，否则返回false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

使用代码演示：

代码语言：javascript

AI代码解释

//priority_queue的头文件是queue #include<queue> void test1() { //默认底层容器是vector，大堆 //创建一个空的堆 priority_queue<int> pq; //插入数据 pq.push(20); pq.push(25); pq.push(19); pq.push(14); pq.push(44); //取堆顶数据 int top = pq.top(); cout << top << endl; //打印数据 while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; //迭代器区间构造 vector<int> v = { 10,20,4,24,21,54 }; priority_queue<int> pq1(v.begin(), v.end()); while (!pq1.empty()) { cout << pq1.top() << " "; pq1.pop(); } }

运行结果：

那这时候就有一个问题，那我们该怎么转换成使用小堆呢？ok，那这时候就需要我们传入第三个模板参数了。

代码语言：javascript

AI代码解释

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

priority_queue中默认第三个模板参数是less<typename Container::value_type>，表示的是小于的操作，如果我们转换成使用小堆，就要传入大于的操作

直接上代码：

代码语言：javascript

AI代码解释

//priority_queue的头文件queue #include<queue> //greater的头文件functional #include<functional> void test2() { //转换成小堆 //第三个模板参数greater<int>，表示的是大于 priority_queue<int,vector<int>,greater<int>> pq; //插入数据 pq.push(20); pq.push(25); pq.push(19); pq.push(14); pq.push(44); //取堆顶数据 int top = pq.top(); cout << top << endl; //打印数据 while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; }

二、优先级队列的底层实现：容器适配与堆算法

2.1 关键接口的代码实现(注意看注释)

代码语言：javascript

AI代码解释

#include<iostream> #include<vector> using namespace std; namespace carrot { template<class T,class Container=vector<T>> class priority_queue { public: void Adjust_up(int child) { int 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; } } } void Adjust_down(int parent) { int child = parent * 2 + 1; while (child < _con.size()) { //找出左右孩子中较大的一个 if (child + 1 < _con.size() && _con[child + 1] > _con[child]) { ++child; } //比较较大孩子和父节点的大小，大就交换，否则不交换 if (_con[parent] < _con[child]) { swap(_con[parent], _con[child]); 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[0], _con[_con.size() - 1]); _con.pop_back(); //向下调整使其还是一个大堆 Adjust_down(0); } size_t top() { return _con[0]; } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: //底层容器 Container _con; }; }

上面的代码实现的是默认大堆操作，那我们该怎么转换成小堆操作呢？是直接将向上调整和向下调整代码中的孩子大于父节点转成孩子小于父节点吗？这很明显有点不太符合实际，那该怎么做呢？

ok，这时候就要引出第三个模板参数，在C++中尽量不用使用函数指针，C++就搞出了仿函数，这个类型的对象就可以像函数一样取使用

那我们该怎么让这个仿函数成为这第三个模板参数呢？看代码

代码语言：javascript

AI代码解释

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; } }; //默认是大堆，第三个模板参数给缺省值为Less<T> template<class T, class Containor = vector<T>, class Compare = Less<T>> class priority_queue { public: //迭代器区间的构造 template <class InputIterator> priority_queue(InputIterator first, InputIterator last) :_con(first, last)//调用_con容器的迭代器区间构造 { //向下调整建堆 for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) { Adjust_down(i); } } //有了迭代器区间的构造，就不会生成默认构造了 priority_queue() { } //向上调整算法 void Adjust_up(int child) { Compare com;//com 这个对象可以像函数一样取使用 int parent = (child - 1) / 2; while (child > 0) { //比较孩子和父亲的大小，大就交换，小就不交换 //if (_con[child] > _con[parent]) //if (_con[parent]<_con[child]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //向下调整算法 void Adjust_down(int parent) { Compare com; int 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[child] > _con[parent]) //if (_con[parent]<_con[child]) if (com(_con[parent], _con[child])) { 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[0], _con[_con.size() - 1]); _con.pop_back(); //向下调整，使其还是一个大堆 Adjust_down(0); } //取堆顶数据 const T& top() const { return _con[0]; } //判断是否为空 bool empty() const { return _con.empty(); } private: Containor _con; };

在上面的代码中，博主实现了两个仿函数：

然后我们就可以用Less<T>作为第三个模板参数：

默认是大堆。

如果想转成小堆结构，就可以显示的传第三个模板参数为greater<类型>：

这样我们就可以转成小堆结构！！！

所谓的仿函数就是这个类型的对象可以像函数一样的调用，ok，接下来我们来看一下仿函数的相关知识（这里只是简单的看一下）