算法学习笔记——对顶堆

对顶堆是由一个大顶堆和一个小顶堆组合而成的数据结构，与传统堆维护最大数不同，对顶堆用于动态维护第k大的数。在对顶堆中，小根堆位于大根堆的上方，要保证小根堆的所有数始终比大根堆大。

对于对顶堆，我们可以用两个优先队列来表示两个堆。而他所维护的，我们可以看成一个单调的序列

这时，我们对两个队列的队列元素数量进行维护（把队首从一个队列中弹出来，加入到另一个队列），那么就可以实现在每次查询第k大/第k小数时，直接访问其中一个队列的队首元素就可以了的。

题目链接：P1168 中位数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

其实，之所以会看到这题，会整对顶堆，都只是因为我想补一下去年zzuli第二周新生赛的防ak题（ZZULIOJ），结果发现那题只是洛谷题加了个背景罢了，连数据都没改，于是，我找到了中位数这题

其实，知道对顶堆怎么操作后，这题就很简单了。每次一个数字来了之后，将其与两个队列的队首进行比较，选择该数字加入的队列，然后一直维护着两个队列元素数量的平衡，两个队列元素数量差不超过2即可。即让每次求中位数时，中位数就是位于元素数量多1的那个的队列的队首就ok啦。

上代码：

#include
#define ll long long
#define endl 'n'
using namespace std;
priority_queue q2;  //相当于大顶堆
priority_queue,greater> q1;  //相当于小顶堆
int n,x,ans,s1,s2;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(i==1) //第一个元素
			q1.push(x),s1++;
		else
		{
			int k1=q1.top();  //每个数都判断加入哪个队列
			if(x>=k1) q1.push(x),s1++;
			else q2.push(x),s2++;
		}
		if(s1-s2==2)  //维护两个队列数量的平衡
		{
			s1--; s2++;
			int k1=q1.top();
			q1.pop(); q2.push(k1);
		}
		if(s2-s1==2)
		{
			s1++; s2--;
			int k1=q2.top();
			q2.pop(); q1.push(k1);
		}
		if(i&1)
		{
			if(s1>s2) ans=q1.top();    //哪个队数量多1，即说明中位数是那个队队首
			else ans=q2.top();
			cout< 
(2)、洛谷P1801 黑匣子 
题目链接：P1801 黑匣子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 
对于这题，我们可以用两个队列维护一个递增的序列，前面的递减队列只维护k个元素，那么每次求第k小就可以直接询问递减队列的队首了。对于添加元素，可以先把元素放入前k小的序列中，然后再将多余的第k+1大的数弹出放入第二个队列中；而对于每次往两个队列中加入每次询问后k的增加，那么就把后面队列的队首放进前面队列即可。
 
上代码：
 
#include
#define ll long long
#define endl 'n'
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+5;
int n,m,k=1,zs,s1,s2,a[N],op[N];
priority_queue q1;
priority_queue,greater> q2;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
		cin>>op[i];
	sort(op+1,op+m+1);
	for(int i=1;i<=n;i++)
	{
		q1.push(a[i]); s1++;  //先放入第一个队列
		if(s1>k)  //如果大于k了，每次就将第k+1大弹出加入第二个队列
		{
			int k=q1.top(); q1.pop();
			q2.push(k);
			s1--; s2++;
		}
		while(zs+1<=m&&op[zs+1]==i)
		{
			zs++; k++;
			cout< 
小结 
虽然说对顶堆这个方法适用范围好像挺小的，一般也见不到这类题，但它的确是一个挺好理解的不错的算法。看看会了就拿来当知识库存吧。。。