admin管理员组文章数量:1623789
前言
最近在刷算法题的时候遇到了需要使用堆来解决的问题(尤其是TOP k 问题)，所以想把这些方法总结一下，防止后面忘记了还得到处找资料。希望能帮助到大家
参考链接1
参考链接2
堆(heap)的介绍
对通常是一个可以被看做一棵树的数组对象，满足两个条件：1，堆中的某个结点的值总是不大于或者不小于其父结点的值 2，堆是一颗完全二叉树
根结点最大的数叫做大根堆，最小的叫做小根堆。
堆排序中建堆的时间复杂度为O(n)
在C++ STL中没有堆的数据结构，所以借助其中的 priority_queue(默认是大根堆)
priority_queue
常用的方法如下：
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
priority_queue使用
- 定义：priority_queue<Type, Container, Functional> ，priority_queue属于是容器适配器，需要指定底层的容器，所以第一个参数Type是queue里面存的数据的类型，第二个参数Container是要使用的底层容器(一般是vector)，Functional 就是比较的方式（准确来说应该是比较方式的类型）.
- 当数据是基本数据类型时可以使用默认的比较方式，使用如下：
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。
//其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
当使用自定的数据类型时，比较方式的写法
- lambda函数（如果有不清楚的可以参考我的这篇文章：c++11新特性）
auto cmp = [](pair<int, int> left, pair<int, int> right) -> bool { return left.second > right.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pri_que(cmp);
- 仿函数实现(最常用)
class mycomparison {
public:
bool operator()(const pair<int, int>& left, const pair<int, int>& right) {
return left.second > right.second;
}
};
priority_queue<pair<int,int>,vector<pair<int, int>>,mycomparison> pri_que2;
- 在自定义类型的类或者结构体中，重载运算符
struct tmp1 //运算符重载<
{
int x;
tmp1(int a) {x = a;}
bool operator<(const tmp1& a) const
{
return x < a.x; //大顶堆
}
}
priority_queue<tmp1> pri_que3;
本文标签： 优先级队列stlpriorityqueue
版权声明：本文标题：STL之优先级队列(priority_queue) 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1728895576a1178364.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论