admin管理员组文章数量:1623789
目录
前言
1、优先队列使用简介
2、优先队列内部原理
2.1 优先队列的容器
2.2 优先队列的数据类型
2.3 优先队列比较类型
3、基于二叉堆的优先队列操作
3.1 top
3.2 push
3.3 adjust_heap(堆维护)
结语
前言
这一次的内容是手动实现priority_queue
priority_queue参考Microsoft visual studio2022文档priority_queue 类 | Microsoft Docs
关于对堆排序和二叉堆的介绍,强烈推荐这个视频排序算法:堆排序【图解+代码】_哔哩哔哩_bilibili
priority_queue即是优先队列,包含在<queue>内
1、优先队列使用简介
原型:
template <class Type, //value type
class Container= vector <Type>,// base container,default:std::vector<Type>
class Compare= less <typename Container ::value_type>>
//比较方式,如果是less则是大根堆
//每次输出的元素都是优先队列中的最大值
//default:std::less<Type>
class priority_queue
众所周知,优先队列每次输出的都是优先级最大的元素,优先级是可以自己定义的,默认是输出最大值,例如:
#include<iostream>
//#include"queue.h"
#include<queue>
#include<vector>
using std::endl;
using std::cout;
int main() {
std::vector<int> nums{ 1,1,4,5,1,4 };
std::priority_queue<int> q(nums.begin(), nums.end());
cout << q.top() << endl;
q.pop();
cout << q.top() << endl;
}
输出结果都是最大值
这里我们可以尝试更换一下比较方式:
这里我不得不吐槽一下,个人觉得比较方式应该设置为第二个模板参数,因为中间的模板参数基础容器一般是没人回去改的,而如果你要更改比较方式,就不得不为了占位置,把中间的参数也填上
#include<iostream>
//#include"queue.h"
#include<queue>
#include<vector>
using std::endl;
using std::cout;
int main() {
std::vector<int> nums{ 1,1,4,5,1,4 };
std::priority_queue<int,std::vector<int>,
std::greater<int>> q(nums.begin(), nums.end());
//设置基础容器是vector,设置比较方式是greater<int>,也就是大于
cout << q.top() << endl;
q.pop();
cout << q.top() << endl;
}
再次查看输出结果,输出了两个1
这里就出现了一个很离谱的设定,明明是less但是每次弹出的都是最大值,明明是greater,却每次出来的都是最小值,这个问题,涉及到priority_queue的底层原理。
2、优先队列内部原理
优先队列可以用一个二叉堆来维护,这样每次取值都只需要花O(1)的时间取堆顶元素花O(logn)的时间维护堆,取最大值就维护一个大顶堆,取最小值就维护一个小顶堆。关于堆的原理,参考本文最初提到的视频连接,堆排序是数据结构里面需要掌握的内容,不论是B站还是CSDN都有数不胜数的教程。后面的内容需要理解堆排序和二叉堆的原理。
2.1 优先队列的容器
优先队列的默认容器是vector,vector是一种在末尾插入和删除时间为O(1)其他位置插入和删除时间为O(n)的支持随机访问的容器
根据堆的原理,也需要在末尾进行插入和删除,并且需要随机访问
作为优先队列的基础数据结构,vector是够用的,也可以用deque,链表只能顺序访问,不能支持堆排序所用到的操作,因此不能使用链表
2.2 优先队列的数据类型
优先队列的数据类型必须是可比较的。具体地,比如我现在自定义了一个结构体complex:
struct complex {
int x, y;
};
int main() {
//std::vector<int> nums{ 1,1,4,5,1,4 };
std::priority_queue<complex> q;
q.push({ 1,2 });
//其余代码和上面插入的测试代码相同
}
运行会报这个错误:
因此需要重载小于运算符
struct complex {
int x, y;
/*bool operator<(const complex &c) {
if (this->x == c.x) {
return this->y < c.y;
}
return this->x < c.x;
}*/
//修改结构体内部,重载小于运算符
friend bool operator<(const complex& a, const complex& b);
};
bool operator<(const complex& a, const complex& b) {
if (a.x == b.x) {
return a.y < b.y;
}
return a.x < b.x;
}
这里我尝试了成员函数重载和友元函数重载,实际结果表示,重载为成员函数依然会报错,因此建议重载为友元函数,本身二元运算符也建议重载为友元函数,因为重载为成员函数时当我们使用operator重载运算符时,左侧的操作数应该是调用对象,这限制了该运算符的使用方式。
2.3 优先队列比较类型
比较类型默认值是std::less<Type>,输出默认是最大值,因此可以手动修改,这里介绍两种方式,一种是简单的使用std::greater<Type>,另一种则是自己写一个函数类,即重载了()运算符的对象。众所周知,重载了()运算符的对象都是函数对象
//首先写一个类,并且重载()运算符
template<class Type>
class MyGreater {
public:
bool operator()(const Type& a, const Type& b) {
return a > b;
}
};
//然后再complex类中重载>运算符
//类中声明friend bool operator>(const complex& a, const complex& b);
bool operator>(const complex& a, const complex& b) {
if (a.x == b.x) {
return a.y > b.y;
}
return a.x > b.x;
}
主函数中调用:
int main() {
//std::vector<int> nums{ 1,1,4,5,1,4 };
std::priority_queue<complex, std::vector<complex>, MyGreater<complex>> q;
complex c1(1, 2);
complex c2(2, 3);
q.push(c1);
q.push({ 2,3 });
auto [x,y]=q.top();//c++17
cout << x << " " << y << endl;
}
输出结果可以看到输出了较小的那一个complex
所以到这里就可以发现那个很坑的问题了,C++的优先队列,如果使用less,那么每次输出的是最大值,如果使用greater,每次输出的是最小值,因为使用less,那么维护的是大根堆,反之则是维护的小根堆
3、基于二叉堆的优先队列操作
二叉堆的原理这里不细说了,只需要知道在二叉堆的内部是一个可随机访问的顺序容器,容器内部第一个值就是堆顶元素。
3.1 top
因此如果要取优先队列的top,可以直接返回容器的第一个元素:
template <class Type, class Container, class Compare>
Type& priority_queue<Type, Container, Compare>::top() {
return Con[0];
}
template <class Type, class Container, class Compare>
const Type& priority_queue<Type, Container, Compare>::top()const {
return Con[0];
}
//前面一堆模板参数其实都不太需要管,这里的Con是一个随机访问顺序容器,可以是vector
//可以是deque或者是什么其他支持随机访问,末尾插入和删除的顺序容器
接下来是pop操作,pop操作需要删除堆顶元素,众所周知,每一趟堆排序的过程就是先把堆顶元素和容器末尾元素交换,然后再删除容器末尾元素,最后再从顶到底维护一次堆。
template <class Type, class Container, class Compare>
void priority_queue<Type, Container, Compare>::pop() {
size_t s = Con.size() - 1;
swap(Con[0], Con[s]);
Con.pop_back();
adjust_heap(0, Compare());
//这里的compare()是用一个重载了括号运算符的类生成一个函数对象的实例
//传递的参数是比较的方式
//如果小于,则维护的堆是大根堆,反之是小根堆
}
3.2 push
接下来是push操作,因为我个人理解在容器首部插入和容器尾部插入差别不是特别大,在容器首部插入的话就自顶向下维护一次堆,在容器尾部插入就自底向上维护一次堆。但是vector首部插入特别慢,所以为了泛用一点,统一为尾部插入比较好。
详情看代码注释部分,也能理解为什么less出来的是小根堆
template <class Type, class Container, class Compare>
void priority_queue<Type, Container, Compare>::push(const Type& right) {
Con.emplace_back(right); //先把元素直接放在容器尾部
size_t s = Con.size();
size_t now = s - 1;
Compare cmp = Compare(); //生成一个函数对象的实例
while (now) {//当 当前节点不是根节点
size_t parent = now / 2;
if (cmp(Con[parent], Con[now])) {//可以借助函数指针来理解。
//如果传入的参数是std::less<Type>
//那么这条语句就变成
//if(Con[parent] < Con[now])
//即是如果父亲小于孩子则交换
//反复下去最大的元素会上浮到堆顶
swap(Con[parent], Con[now]);
now = parent;
}
else {
break;
//当遇到不需要交换的时候,即是上浮到正确的位置
//就可以停止上浮了
}
}
}
3.3 adjust_heap(堆维护)
最后详细讲一下前面提到的维护堆:adjust_heap
template <class Type, class Container, class Compare>
void priority_queue<Type, Container, Compare>::adjust_heap(size_t root, const Compare& cmp) {
size_t left = root * 2 + 1;//找作儿子
size_t right = root * 2 + 2;//找右儿子
size_t len = Con.size();
size_t large = root; //记录一个值来寻找父亲和两个儿子之中最大或是最小的那个
if (left < len && cmp(Con[large], Con[left])) {
//cmp的解释同上
//可带入if(Con[large] < Con[left]),std::less<Type>建大根堆
//if(Con[large] > Con[left]),std::greater<Type>建小根堆
large = left;
}
if (right < len && cmp(Con[large], Con[right])) {
large = right;
}
//如果父亲节点的值不能作为堆顶元素
if (large != root) {
swap(Con[root], Con[large]); //将堆顶元素放在父亲节点
adjust_heap(large, cmp);//从交换的位置开始自顶向下维护堆
}
}
看到这里,可以简单的概括一下,再建堆的时候,如果使用std::less<Type>,即是如果 小于 则 交换。这个小于是父亲小于儿子,所以是把儿子的值给父亲,因此父亲节点是二叉堆堆里面任意一个子二叉堆的最大值,所以最终建立出来的就是大根堆,内部源码实现其实可以改变比较顺序,改成儿子小于父亲,那么这样less建出来的就是小根堆。
结语
出于晚上的实验课过早完成实验,于是决定写一个篇blog打发时间,顺手记录自己实现优先队列的过程,本来是打算从构造函数到二叉堆,写一篇完整的优先队列实现全过程,但这样写篇幅会非常非常大,于是省去了很多细节,很多解释直接放在代码注释中了,并且还有四十分钟就下课了,再展开过多可能写不完,
如果有错误的地方,欢迎各位大佬提出意见,现在的我完完全全就是一个菜菜,出现错误也是情理之中。
本文标签: 原理简单priorityqueuestd是大根堆
版权声明:本文标题:C++手动实现priority_queue,以及简单理解内部原理和为什么std::less是大根堆 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728895034a1178300.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论