priority_queue

sLMxf · 2023-08-15 15:56:31 · 个人记录

什么是 priority_queue（优先队列）
优先队列是在正常队列的基础上加了优先级，保证每次的队首元素都是优先级最大的。每次操作队列中的元素都是按优先级排序的。
priority_queue 基本用法
- 建立
  肥肠简单：
```
priority_queue<类型> a;
```
- 调用队首
  直接调用a.top()。
- 插入删除
  1. 插入
    直接使用 a.push(x);。
  2. 删除
    只能删除队首，使用 a.pop()。
- 返还长度，判断为空
  也是很简单，长度使用 a.size()，判空使用 a.empty()，如果是空返回 1。
priority_queue 优先级
1. 从大到小（int）
  直接在定义处写priority_queue<int>a;便可。
2. 从小到大（int）
  将定义改成priority_queue<int,vector<int>,greater<int> >a;便可。
3. 结构体自定义
  结构体一般有两个数，没办法像从小到大那样。~~那怎么办，只能带上赌徒四件套了吗？~~ 但是你可以先重载这个结构体中的<，之后便归于正常了：
```
//仅为模板
struct node{
    int w,c;
    bool operator<(const node a)const{
         if(c!=a.c) return c<a.c;
         else return w<=a.w;
    }
}
```
priority_queue应用：

题目描述（原题：【模板】堆）

给定一个数列，初始为空，请支持下面三种操作：
1. 给定一个整数 x，请将 x 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 1 个）。
数据范围
- 对于 30\% 的数据，保证 n \leq 15。
- 对于 70\% 的数据，保证 n \leq 10^4。
- 对于 100\% 的数据，保证 1 \leq n \leq 10^6,1\leq x\leq 2^{31}-1,op\in\{1,2,3\}。
解法

直接开一个优先队列，按照题意模拟便可。
priority_queue练习
- 序列合并
- 黑匣子

priority_queue

题目描述（原题：【模板】堆）

数据范围

解法