imicola 1.4 优先队列(堆) priority_queue
1.4 优先队列(堆) priority_queue

1.4 优先队列(堆) priority_queue

289 字 · 约 1 分钟

include <queue>

1.4.1 构造

priority_queue<类型,容器,比较器>

  • 类型:要储存的数据类型
  • 容器:储存数据的底层容器,默认为 vector<T>,竞赛时保存默认即可
  • 比较器: 比较大小使用的比较器,默认为 less<T>,可以自定义
priority_queue<int> pque1;
priority_queue<int,vector<int>,greater<int>> pque2;//变小顶堆
cpp

自定义比较器尽量不用,容易犯迷糊

1.4.2 常用语法

作用 用法 示例
进堆 .push(元素) que.push(1);
出堆 .pop() que.pop();
取堆顶(最大值/最小值) .top() int a = que.top();
查看大小/判空 和vector一致 略
适用场景
  • 保持数据的有序性,每次向队列中插入大小不定的元素,或每次从队列取出最大/最小的元素,元素数量为nn,插入操作数量为kk
    • 使用快排:k⋅nlog⁡nk\cdot n \log n
    • 使用优先队列:k⋅log⁡nk\cdot \log n

1.4.3 注意事项

  • 仅堆顶可读
cout << qpue[1] <<endl; //错误
cpp
  • 所有元素不可写
qpue[1] = 2;
pque.top() = 1;
//均为错误
cpp

但如果要修改堆顶元素

int tp = pque.top(); //保存堆顶
pque.pop(); //弹出堆顶
qpue.push(tp + 1); //通过保存的堆顶修改堆顶
cpp

知识关联

1 反向链接 · 0 提及笔记
局部关系图谱 悬停高亮 · 点击跳转