优先队列(堆的使用)

发布时间 2024-01-01 21:24:04作者: zzzr0111

如何定义

大根堆:每个节点的值都大于等于其子节点的值,在大根堆中,最大值总是在堆顶
小根堆:每个节点的值都小于等于其子节点的值,在小根堆中,最小值总是在堆顶

#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()删除堆顶元素(此时优先队列不能为空)