优先级队列
优先级队列priority_queue也是STL库中容器适配器的一种，常用于进行数据优先级的处理，说到这儿是不是发现有些熟悉，没错它和我们之前讲解的堆本质上就是一个东西，底层都是数组存储的完全二叉树，它在STL库中进行了完美的封装并加入了泛型编程的思想呈现出来
文章目录：
- 优先级队列
- 1. 优先级队列的使用
- 1.1 构造函数
- 1.2 常用接口
- 1.3 优先级切换
- 2. 优先级队列模拟实现
- 2.1 push方法
- 2.2 pop方法
- 2.3 判空大小堆顶
- 2.4 仿函数
- 2.5 完整代码
1. 优先级队列的使用
-
优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
-
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
-
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
-
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素 -
标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
-
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
1.1 构造函数
优先级队列有两种构造方式，可以使用默认构造一个空对象，也可以通过迭代器区间进行构造
默认构造
int main()
{
priority_queue<int> pq; //默认构造一个空对象
cout << typeid(pq).name() << endl;
return 0;
}
默认的比较方式为less，会生成大堆
迭代器区间构造
int main()
{
vector<int> v = { 1, 2, 3, 4, 5, 6 };
priority_queue<int, deque<int>, greater<int>> pq(v.begin(), v.end()); //生成小堆
cout << typeid(pq).name() << endl;
while (!pq.empty())
{
//打印堆中元素
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
这里将比较方式改为 greater 后，就会生成 小堆
1.2 常用接口
这里列举常用接口的使用，感兴趣的大佬们可以前往官方文档了解更多细节
empty()接口：判空size()接口：查看大小top()接口：查看堆顶元素push()：向堆中插入元素pop()：删除堆顶元素
int main()
{
vector<int> v = { 24,45,33,12,65,88,52,66 };
priority_queue<int> pq(v.begin(), v.end()); //默认生成大堆
cout << "empty：" << pq.empty() << endl; //判空
cout << "size：" << pq.size() << endl; //查看大小
cout << "top：" << pq.top() << endl; //查看堆顶元素
cout << "------------------------" << endl;
//插入操作
pq.push(8);
pq.push(112);
cout << "empty：" << pq.empty() << endl;
cout << "size：" << pq.size() << endl;
cout << "top：" << pq.top() << endl;
cout << "------------------------" << endl;
//删除堆顶元素
pq.pop();
pq.pop();
cout << "empty：" << pq.empty() << endl;
cout << "size：" << pq.size() << endl;
cout << "top：" << pq.top() << endl;
cout << "------------------------" << endl;
return 0;
}
1.3 优先级切换
创建优先级队列时，默认的比较方式缺省值为less，使用的是仿函数，默认生成大堆，想要创建小堆的话，需要将比较方式设置为grater，不过小于less是大堆，大于grater是小堆，嗯…这就点奇怪
注意：
如果要修改比较方式的话，模板参数2的底层容器也需要指明，因为比较方式是模板参数3，缺省参数规定不能跳跃缺省
priority_queue<int, deque<int>, greater<int>> pq(v.begin(), v.end()); //生成小堆
2. 优先级队列模拟实现
我们先来实现没有加入仿函数的版本
2.1 push方法
插入数据，只需尾插数据，然后遵循大小堆的规则将父子节点进行比较，向上调整即可
//向上调整
void adjust_up(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//大堆 parent > chiled
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
2.2 pop方法
删除数据，只需将堆顶数据交换到堆底，删除堆底元素，然后遵循大小堆的规则将父子节点进行比较，从堆顶向下调整即可
//向下调整
void adjust_down(int parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size()
&& _con[child + 1] > _con[child) //找出较大的孩子
{
++child;
}
//大堆 parent > child
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
2.3 判空大小堆顶
empty()方法：判空，复用底层容器的判空接口即可
bool empty()
{
return _con.empty();
}
size()方法：查看大小，复用底层容器查看大小接口即可
size_t size()
{
return _con.size();
}
top()方法：查看堆顶元素：返回数组首元素即可
const T& top()
{
return _con[0];
}
想要使用小堆的话需要将代码中的 > 改为 <，这样的手动切换方式，就显得太挫了，那么是否有姐解决方法呢？答案是有的，那就是本文的周重头戏，使用仿函数来解决
2.4 仿函数
仿函数的主要作用是 借助类和运算符重载，做到同一格式兼容所有函数
下面我们用两个比较大小的仿函数来解决上面优先级队列的实现中不能大小堆自由切换的问题
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
template<class T, class Container = vector<T>, class Comapre = less<T>>
当需要进行逻辑比较时，只需要调用 operator() 进行比较即可
下面来改写向上调整和向下调整
void adjust_up(int child)
{
Comapre com;
int parent = (child - 1) / 2;
while (child > 0)
{
//child > parent -> parent < child
//if (Comapre()(_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)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
Comapre com;
if (child + 1 < _con.size()
&& com(_con[child], _con[child + 1])) //找出较大的孩子
{
++child;
}
//parent < child
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
这样就可以实现大小堆的自由切换了
2.5 完整代码
#pragma once
#include <iostream>
#include <list>
#include <vector>
#include <deque>
#include <algorithm>
#include <string>
using namespace std;
namespace sakura
{
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 Comapre = less<T>>
class priority_queue
{
public:
void adjust_up(int child)
{
Comapre com;
int parent = (child - 1) / 2;
while (child > 0)
{
//child > parent -> parent < child
//if (Comapre()(_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)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
Comapre com;
if (child + 1 < _con.size()
&& com(_con[child], _con[child + 1])) //找出较大的孩子
{
++child;
}
//parent < child
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
C++【STL】之priority_queue学习，到这里就介绍结束了，本篇文章对你由帮助的话，期待大佬们的三连，你们的支持是我最大的动力！
文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正！
