admin管理员组文章数量:1623788
文章目录
- priority_queue 基本用法
- 大顶堆
- 小顶堆
- vector 排序
- 优先队列自定义排序
priority_queue 基本用法
头文件<queue>
priority_queue< type, container, function>
- type 类型
- container:实现优先队列的底层容器(缺省)
- function:元素之间的比较方式(缺省)
对于container,要求必须是数组形式实现的容器,例如vector、deque,而不能使list。
在STL中,默认情况下(不加后面两个参数)是以vector为容器,以 operator< 为比较方式,所以在只使用第一个参数时,优先队列默认是一个最大堆,每次输出的堆顶元素是此时堆中的最大元素。
成员函数
假设type类型为int,则:
-
bool empty() const
返回值为true,说明队列为空; -
int size() const
返回优先队列中元素的数量; -
void pop()
删除队列顶部的元素,也即根节点 -
int top()
返回队列中的顶部元素,但不删除该元素; -
void push(int arg)
将元素arg插入到队列之中;
大顶堆
头文件<functional>
中,包含less<int>
和greater<int>
//构造一个空的优先队列(此优先队列默认为大顶堆)
priority_queue<int> big_heap;
//另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2;
int类型,大顶堆
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
void t_Big_heap(){
vector<int> vals = {11, 33, 55, 22, 44};
// 大顶堆
priority_queue<int, vector<int>, less<int>> big_heap;
for(auto &e: vals) big_heap.push(e);
// show
cout << "big_heap.size() :" << big_heap.size() << endl;
cout << "big_heap.empty() :" << big_heap.empty() << endl;
while(!big_heap.empty()){
cout << big_heap.top() << " ";
big_heap.pop();
}
}
----------------------------------------------------------------
big_heap.size() :5
big_heap.empty() :0
55 44 33 22 11
小顶堆
//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;
存储vector<int>
void t_Sml_heap_v2(){
// 小顶 按照 [0] 先升序,相等时再按照[1] 升序
vector<vector<int>> vec2i= {{11, 13}, {12, 14}, {11, 12}, {15, 16}};
// 小顶堆
// priority_queue<int, vector<vector<int>>, greater<vector<int>>> Sml_heap;
priority_queue<int, vector<vector<int>>, greater<>> Sml_heap;
for(auto &e: vec2i) Sml_heap.push(e);
// show
cout << "big_heap.size() :" << Sml_heap.size() << endl;
cout << "big_heap.empty() :" << Sml_heap.empty() << endl;
while(!Sml_heap.empty()){
cout << Sml_heap.top()[0] << " - " << Sml_heap.top()[1] << endl;
Sml_heap.pop();
}
}
----------------------------------------------------------------
big_heap.size() :4
big_heap.empty() :0
11 - 12
11 - 13
12 - 14
15 - 16
vector 排序
一维的排序
void sort_vec(){
vector<int> vals = {11, 33, 55, 22, 44};
// sort(vals.begin(), vals.end(), less<>()); // 升序(默认)
// sort(vals.begin(), vals.end(), greater<>()); // 降序
// sort(vals.begin(), vals.end()); // 升序
sort(vals.begin(), vals.end(), [&](int &a, int &b){
return a < b;
}); // 升序
for(auto &e: vals) cout << e << " ";
};
-------------------------------------------------------------
11 22 33 44 55
二维的排序
void sort_vec(){
vector<vector<int>> vec2i= {{11, 13}, {12, 14}, {11, 12}, {15, 16}};
// sort(vec2i.begin(), vec2i.end()); // [0] [1] 均升序
sort(vec2i.begin(), vec2i.end(), [&](auto &a, auto &b){
return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
}); // [0] [1] 均升序
// sort(vec2i.begin(), vec2i.end(), [&](auto &a, auto &b){
// return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
// }); // [0]升序 如果相等[1]降序
for(auto &vec: vec2i){
cout << vec[0] << " - " << vec[1] << endl;
}
};
-------------------------------------------------------------
11 - 12
11 - 13
12 - 14
15 - 16
优先队列自定义排序
vector实现
void t_vec(){
vector<string> strs = {"xhh", "mmcy", "mi", "xhz", "abcdef"};
// 排序;长度降序,长度相同时 字典序升序
sort(strs.begin(), strs.end(), [&](string &s1, string &s2){
return (s1.size() > s2.size()) || (s1.size() == s2.size() && s1 < s2);
});
for(auto str: strs){
cout << str.size() << " " << str << endl;
}
}
-------------------------------------------------------------
6 abcdef
4 mmcy
3 xhh
3 xhz
2 mi
priority_queue实现
struct cmp{
bool operator()(const string& s1, const string& s2) const{
// 和vector排序写法相反
// a < b : [vec] 升序 [pri] 大顶堆
return (s1.size() < s2.size()) || (s1.size() == s2.size() && s1 > s2);
}
};
void t_prique(){
vector<string> strs = {"xhh", "mmcy", "mi", "xhz", "abcdef"};
priority_queue<string, vector<string>, cmp> pri_que(strs.begin(), strs.end());
while(!pri_que.empty()){
cout << pri_que.top().size() << " " << pri_que.top() << endl;
pri_que.pop();
}
}
-------------------------------------------------------------
6 abcdef
4 mmcy
3 xhh
3 xhz
2 mi
本文标签: 队列priorityqueue小顶堆大顶堆
版权声明:本文标题:【C++】优先队列、priority_queue(大顶堆,小顶堆) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728895676a1178376.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论