如何定义
大根堆:每个节点的值都大于等于其子节点的值,在大根堆中,最大值总是在堆顶
小根堆:每个节点的值都小于等于其子节点的值,在小根堆中,最小值总是在堆顶
#include <queue>//头文件
//通用写法
std::priority_queue<TypeName> q; ∕∕ 数据类型为 TypeName
std::priority_queue<TypeName, Container> q; ∕∕ 使用 Container 作为底层容器
std::priority_queue<TypeName, Container, Compare> q;
//使用 Container 作为底层容器,使用 Compare 作为比较类型
//默认使用底层容器 vector
//比较类型 less<TypeName>(此时为它的 top() 返回为最大值)
//若希望 top() 返回最小值,可令比较类型为 greater<TypeName>
//注意:不可跳过 Container 直接传入 Compare
//例如,TypeName为int时
priority_queue<int> q1 // 大根堆
priority_queue<int, vector<int>, greater<int>> q2 // 小根堆
功能函数
top()访问堆顶元素(此时优先队列不能为空)
empty()询问容器是否为空
size()查询容器中的元素数量
对数级复杂度的函数
push(x) 插入元素x,并对底层容器排序
pop()删除堆顶元素(此时优先队列不能为空)