原文已废，有需自取
markdown:qwq，我竟然值10000
没错，我想钱想疯了，哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
一、什么是优先队列
优先队列是特殊队列，不按照先进先出的规则弹出元素，每次会取出当前队列里优先级最高的数字。
底层数据结构依靠二叉堆实现，C++ 标准库的 priority_queue 就是基于堆封装的工具。
二、priority_queue 基础使用
需要引入头文件<queue>，也可以直接用万能头 bits/stdc++.h
基础操作功能：
1.push (x)：插入元素 x，运行效率 O (log n)
2.pop ()：删掉优先级最高的元素，运行效率 O (log n)
3.top ()：读取优先级最高的元素，运行效率 O (1)
4.empty ()：判断队列是否为空
5.size ()：统计队列内元素总个数
重要注意点：和普通 queue 不一样，优先队列只能用 top () 取顶端元素，不存在 front () 和 back () 两个函数，程序只维护优先级最高的数值。
三、两种优先级写法（大根堆、小根堆）
1. 大根堆（默认写法，数值大的优先取出）
priority_queue<int,vector<int>,less<int> > q;
简化写法：priority_queue<int,vector<int>> q;
2. 小根堆（数值小的优先取出）
priority_queue<int,vector<int>,greater<int> > q;
做题时根据题目需求选择对应写法即可。
四、实战练习：洛谷 P1168 中位数
题目地址：https://www.luogu.com.cn/problem/P1168
1. 题目要求
依次输入 n 个数字，每当输入总数为奇数时，输出此时全部数字的中位数。
2. 解题分析
如果每次输入都直接排序会超时，最优解法是同时使用一个大根堆、一个小根堆。
3. 解题思路
大根堆存放偏小的一半数字，小根堆存放偏大的一半数字；全程平衡两个堆的元素数量，输入奇数个数字时，大根堆最顶端的数就是中位数。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
priority_queue<int>da; //大根堆
priority_queue<int,vector<int>,greater<int>>xiao; //小根堆
for (int i=1;i<=n;i++)
{
int x;
cin>>x; //输入要插入的值
if(da.empty()||x<=da.top()) //判断进入大根堆还是小顶堆
{
da.push(x);
}
else
{
xiao.push(x);
}
if(da.size()>xiao.size()+1) //判断两堆数字个数
{
xiao.push(da.top());
da.pop();
}
else if(xiao.size()>da.size())
{
da.push(xiao.top());
xiao.pop();
}
if(i%2==1)
{
cout<<da.top()<<endl; //输出
}
}
return 0;
}如果听完还是不懂的，可以参考[P1168 中位数 题解](https://www.luogu.com.cn/problem/solution/P1168)
byebye,有问题发到评论区
© 版权声明
文章版权归作者所有，未经允许请勿转载。
文章版权From Writer，未经OK Don`t转载
THE END
暂无评论内容