当前位置：网站首页>[STL]优先级队列priority_queue
[STL]优先级队列priority_queue
2022-07-26 03:10:00 【Protein_zmm】
一、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是大堆。
// 默认是大堆
void test_priority_queue()
{
priority_queue<int> pq; // 头文件queue
pq.push(3);
pq.push(3);
pq.push(7);
pq.push(1);
pq.push(9);
while (!pq.empty())
{
cout << pq.top() << " "; // 取优先级最高的，默认是大的优先级高
pq.pop();
}
cout << endl;
}
如果想让小的优先级高怎么办？
控制小的优先级高——传greater的仿函数
#include <functional> // greater的头文件
void test_priority_queue()
{
// 要传第三个模板参数前提是要有第二个模板参数
priority_queue<int, vector<int>, greater<int>> pq; // 最好不去使用deque，因为堆可能数据很大
pq.push(3);
pq.push(3);
pq.push(7);
pq.push(1);
pq.push(9);
while (!pq.empty())
{
cout << pq.top() << " "; // 取优先级最高的，默认是大的优先级高
pq.pop();
}
cout << endl;
}
三、topK - 数组中的第K个最大元素
215. 数组中的第K个最大元素
方法一：先排序
sort(迭代器区间)：默认升序，要降序就传greater的仿函数
O(NlogN)
// 排升序
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
// 下标 0 1 2 3 4 size = 5, k = 1
// 元素 1 2 3 4 5 第一个大的就是5
// 排降序
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>()); // 仿函数是一个自定义类型
return nums[k - 1];
}
};
// 0 1 2 3 4 size = 5, k = 1 第一个大的就是k - 1 对应的元素 5
// 5 4 3 2 1
对比刚刚priority_queue和sort中传的greater可以发现明显的不一样，原因是：
方法二：大堆
建堆时间O（N）+ O(KlogN)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> maxHeap(nums.begin(), nums.end()); // 建N个数的大堆
// 将前k-1个删掉
while (--k) // 走k-1次
{
maxHeap.pop();
}
return maxHeap.top();
}
};
方法三：建K个数的小堆
O(K)的空间复杂度
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 如果n很大，且n远大于K
// 建一个K个数的小堆
priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.begin() + k); // O(K)
// 剩下的N-K个数，依次与堆顶数据比较，比他大就替换他进堆
for (size_t i = k; i < nums.size(); ++i)
{
if (nums[i] > minHeap.top())
{
minHeap.pop();
minHeap.push(nums[i]);
}
} // O((N-K) * logK)
// 前K个大的数都在堆里面，求第K个大的就是堆顶的值(因为是小堆)
return minHeap.top();
}
// O( K + (N-K) * logK)
};
四、priority_queue模拟实现
namespace zmm
{
// 默认大堆
template<class T, class Container = vector<T>>
class priority_queue
{
private:
// 不希望别人随意去调用他
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent) // 前提：左右子树都是小堆或是大堆
{
size_t child = 2 * parent + 1; // 默认指向左孩子
while (child < _con.size()) // 调到叶子停止
{
if (child + 1 < _con.size() && _con[child + 1] > _con[child])
{
child++;
}
if (_con[child] > _con[parent])
{
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
public:
priority_queue()
{
}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)
{
// 要构建为堆
// 从最后一个非叶子开始调整建堆
// i 不能用size_t
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{
adjust_down(i);
}
}
void push(const T& x)
{
// 插入末尾后，向上调整到根
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
assert(!_con.empty());
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; // 自定义类型会调用它的构造函数
};
}
在这里我们实现的是大堆，但是如果要改为小堆，还需要改adjustup和adjustdown中的符号关系，这就比较麻烦了，所以我们采用一种仿函数的方式来解决这个问题
4.1 仿函数
struct Less
{
bool operator()(int x, int y)
{
return x < y;
}
};
struct Greater
{
bool operator()(int x, int y)
{
return x > y;
}
};
int main()
{
// 在这里，less和gt像函数名，或像函数指针，可以像函数一样去调用
Less less; // Less是一个类，定义一个对象
cout << less(1, 2) << endl;
Greater gt;
cout << gt(1, 2) << endl; // 等价于gt.operator()(1,2)
return 0;
}
在这里，Less称为仿函数类型，less叫做函数对象
上述代码只适用于int类型，因此我们在添加上模板参数
template<class T>
struct Less
{
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
template<class T>
struct Greater
{
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
int main()
{
Less<int> less; // Less是一个类，定义一个对象
cout << less(1, 2) << endl;
// 或者可以这样写
cout << Less<int>()(1, 2) << endl;
cout << Less<double>()(1.1, 1.2) << endl;
Greater<int> gt;
cout << gt(1, 2) << endl; // 等价于gt.operator()(1,2)
return 0;
}
仿函数是一个类型，类型可以通过模板参数来传递
这样子，我们就可以通过仿函数的方式，修改了模拟实现的代码
namespace zmm
{
// 默认大堆 -> Less
// 仿函数是一个类型->可以通过模板参数传递
template<class T>
struct Less
{
// 左＜右
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
// 小堆
template<class T>
struct Greater
{
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
template<class T, class Container = vector<T>, class Compare = Less<T>> // 默认是Less大堆
class priority_queue
{
private:
// 不希望别人随意去调用他
void adjust_up(size_t child)
{
Compare com;
size_t 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(size_t parent) // 前提：左右子树都是小堆或是大堆
{
Compare com;
size_t child = 2 * parent + 1; // 默认指向左孩子
while (child < _con.size()) // 调到叶子停止
{
// if (child + 1 < _con.size() && _con[child + 1] > _con[child])
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[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
public:
priority_queue()
{
}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)
{
// 要构建为堆
// 从最后一个非叶子开始调整建堆
// i 不能用size_t
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{
adjust_down(i);
}
}
void push(const T& x)
{
// 插入末尾后，向上调整到根
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
assert(!_con.empty());
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; // 自定义类型会调用它的构造函数
};
}
4.2 仿函数的应用
如果数据类型不支持比较，或者比较的方式不是你想要的，可以通过仿函数，自己去控制比较逻辑
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);
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day << endl;
return _cout;
}
void test_priority_queue2()
{
priority_queue<Date, vector<Date>> pq;
pq.push(Date(2022, 3, 26));
pq.push(Date(2021, 10, 26));
pq.push(Date(2023, 3, 26));
while (!pq.empty())
{
cout << pq.top();
pq.pop();
}
cout << endl;
}
struct LessPDate
{
bool operator()(const Date* d1, const Date* d2) const
{
return *d1 < *d2;
}
};
void test_priority_queue3()
{
priority_queue<Date*, vector<Date*>, LessPDate> pq;
pq.push(new Date(2022, 3, 26));
pq.push(new Date(2021, 10, 26));
pq.push(new Date(2023, 3, 26));
while (!pq.empty())
{
cout << *pq.top(); // 这时候就不是按大小排了，这里是比较的指针（地址）大小
// 那想要进行日期大小比较怎么办？ —— 增加 class LessPDate
// 如果数据类型不支持比较，或者比较的方式不是你想要的，可以通过仿函数，自己去控制比较逻辑
pq.pop();
}
cout << endl;
}
int main()
{
test_priority_queue3();
return 0;
}
边栏推荐
- LeetCode·83双周赛·6128.最好的扑克手牌·模拟
- STM32——串口学习笔记(一个字节、16位数据、字符串、数组）
- LeetCode·每日一题·919.完全二叉树插入器·层次遍历·BFS
- Hcip day 8 notes sorting (OSPF routing control, Appendix E, anti ring, shortest path calculation, republication))
- 如何用U盘进行装机？
- STM - exti external interrupt learning notes
- 【TensorFlow＆PyTorch】图像数据增强API
- ByteDance (Tiktok) software test monthly salary 23K post, technical two-sided interview questions are newly released
- Summary of Huawei virtualization fusioncompute knowledge points
- 了解预加载和懒加载、学会缓动动画
猜你喜欢
js中数组排序的方法有哪些
Opencv saves pictures in the specified format
Opening method of win11 microphone permission
![[noip2001 popularization group] packing problem](/img/b7/1310b3e68d0ee016465fc069315af6.png)
[noip2001 popularization group] packing problem
Summary of Huawei virtualization fusioncompute knowledge points
canvas——绘制曲线——挂钟，饼图，五角星
【C语言】深入理解 整型提升 和 算术转换
Win11 method of changing disk drive letter
OxyCon 2022 网络抓取前沿大会即将开启！
LeetCode·
随机推荐
OxyCon 2022 网络抓取前沿大会即将开启！
How to correctly calculate the CPU utilization of kubernetes container
JVM内存模型解析
[NOIP2001 普及组]装箱问题
[Yuri crack man] brings you easy understanding - deep copy and shallow copy
在混合云中管理数据库：八个关键注意事项
Teach you to rely on management hand in hand
Multithreaded programming
一篇文章让你理解 云原生 容器化相关
Win11大小写提示图标怎么关闭？Win11大小写提示图标的关闭方法
文件操作（一）——文件简介与文件的打开方式和关闭
Quick check of OGC WebGIS common service standards (wms/wmts/tms/wfs)
After clicking play, the variables in editorwindow will be destroyed inexplicably
Leetcode · daily question · sword finger offer | | 115. reconstruction sequence · topological sorting
Keyboardtraffic, a tool developed by myself to solve CTF USB keyboard traffic
URDF 语法详解
Oxycon 2022 network capture frontier conference is about to open!
Unknown-Aware Object Detection:Learning What You Don’t Know from Videos in the Wild(CVPR 2022)
An article allows you to understand the relevance of cloud native containerization
Get twice the result with half the effort: learn the web performance test case design model