admin管理员组文章数量:1623797
写程序经常会用到priority_queue,大小顶堆,由于用的不熟,今天总结一下留个纪念。
一、基本使用
priority_queue
对于基本类型的使用方法相对简单。他的模板声明带有三个参数,priority_queue<Type, Container, Functional>
,Type
为数据类型, Container
为保存数据的容器,Functional
为元素比较方式。Container
必须是用数组实现的容器,比如 vector
, deque
但不能用 list.STL里面默认用的是 vector
. 比较方式默认用 operator<
, 所以如果你把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。
比如这样
priority_queue<int>q;//这是一个int的大顶堆
二、小顶堆
小顶堆的实现有两种方式:
- 元素取相反数,比如输入1,2,3,你把取反传进去-1,-2,-3大顶堆取出来数-1,再次取反自然就是你想要的数。
- 利用定义实现,根据我们上面的定义
priority_queue<int, vector<int>, greater<int> > q;
greater时一个仿函数。
三、自定义类型
必须自己重载 operator< 或者自己写仿函数(有些编译器重载运算符会很坑,还是两个都掌握的比较稳妥)。
- 重载运算符,推荐采用下面这种方法:
struct cow {
int s, e;
cow(int a = 0, int b = 0) { s = a, e = b; }
}c[MAX];
bool operator<(const cow & c1, const cow & c2) {
return c1.s < c2.s;
}
priority_queue<cow>q;
此时我们将其当作基本类型使用即可。
- 自己写仿函数,也就是刚才出现的
greater<int>
这种函数,怎么写呢?
struct cow {
int s, e;
cow(int a = 0, int b = 0) { s = a, e = b; }
}c[MAX];
struct cmp {
bool operator()(cow c1, cow c2) {
return c1.s < c2.s;
}
};
priority_queue<cow, vector<cow>, cmp>p;
本文标签: 自定义类型priorityqueue大顶堆
版权声明:本文标题:priority_queue:如何创建大顶堆?如何创建自定义类型的堆? 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728897402a1178587.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论