leetcode刷题笔记——优先队列priority

队列priority"/>

leetcode刷题笔记——优先队列priority

定义：

priority_queue<Type, Container, Functional>
Type：数据类型
Container：容器
Functional：比较方式

当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

基础类型：默认是大顶堆： 

priority_queue<int> a; 
等同于：
priority_queue<int,vector<int>,less<int>> a;

priority_queue常用函数：

push()

top()

pop()

empty()

size()

priority_queue内元素优先级的设置：

（1）基本数据类型的优先级设置

大顶堆：
priority_queue<int,vector<int>,less<int>> q;小顶堆：
priority_queue<int,vector<int>,greater<int>> q;

（2）结构体的优先级设置

结构体内重载运算符：

struct fruit{string name;int price;friend bool operator < (fruit f1,fruit f2){return f1.price < f2.price;}
}; 定义优先队列：
priority_queue<fruit> pq;

重载大于号会编译错误，只需要小于号就能完成比较：

f1 > f2等价于：
f2 < f1;f1==f2等价于：
!(f1 < f2)&&!(f2 < f1);

结构体外重载运算符【推荐】：

小括号对等价于小于号
所以下述代码是建小根堆
struct cmp{bool operator() (fruit f1, fruit f2){return f1.price > f2.price;}
};此时定义优先队列：
priority_queue<fruit , vector<fruit> , cmp> pq;

注意事项：

1. 如果结构体内数据较为庞大，建议使用引用来提高效率，比较类参数加上 "const"  和 "&"

2. 使用top()函数前，必须使用empty()判断优先队列是否为空