对顶堆，顾名思义，就是建立一个大根堆和一个小根堆。

介绍

如果把堆中的大根堆想成一个上宽下窄的三角形，把小根堆想成一个上窄下宽的三角形，那么对顶堆就可以具体地被想象成一个“沙漏”，通过这两个堆的上下组合，我们可以把一组数据分别加入到对顶堆中的大根堆和小根堆，以维护我们不同的需要。

页首图是形象的解释。

那么对顶堆是干嘛用的呢？

来一个…

例题

题意：给出一个长度为 $N$ 的非负整数序列 $A_i$ ，对于所有 $1 ≤ k ≤ (N + 1) / 2$ ，输出 $A_1, A_1 \sim A_3, …,A_1 \sim A_{2k - 1}$ 的中位数。即前 $1,3,5,…$ 个数的中位数。对于 $100\%$ 的数据， $N ≤ 100000$ 。

题解与代码

对于这道题，我们可以在每次输入时进行一次排序。然后奇数时输出中间的数。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	int a[100000+5],n;
	void yzmain()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",a+i);
			int tmp=a[i],j;
			for(j=i-1;j>=0&&tmp<a[j];j--)
				a[j+1]=a[j];
			a[j+1]=tmp;
			if(i%2!=0)
				printf("%d\n",a[(1+i)/2]);
		}
   		return;
	}
}
int main()
{ 
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

~~这样这道题就完美的结束了。~~

正解与代码

这道题主要做法就是先来一个大根堆和一个小根堆，而对于一个序列，我们把大数放在小根堆里，小数放在大根堆里，并且保证小根堆的元素个数与大根堆的差一。

根据数学中不等式的传递原理，假如一个集合 $A$ 中的最小元素比另一个集合 $B$ 中的最大元素还要大，那么就可以断定： $A$ 中的所有元素都比 $B$ 中元素大。所以，我们把小根堆“放在”大根堆“”上面”，如果小根堆的堆顶元素比大根堆的堆顶元素大，那么小根堆的所有元素要比大根堆的所有元素大。

我们很容易发现，当序列的长度为奇数时，元素多的堆顶就是序列的中位数。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	int n;
	priority_queue<int>mx,mn; //实际上，优先队列内部实现是堆
	void yzmain()
	{
		int tmp;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&tmp);
			if(mn.empty()||tmp>mn.top()) mx.push(-tmp);
            else mn.push(tmp);
            //如果不注意堆为空的情况，RE 快乐。
            //看看我的提交记录：https://www.luogu.com.cn/record/list?pid=P1168&user=185868
			while(mx.size()<mn.size()&&mn.size()>0) mx.push(-mn.top()),mn.pop();
			while(mx.size()>mn.size()&&mx.size()>0) mn.push(-mx.top()),mx.pop();
			if(i%2==1) printf("%d\n",(mx.size()>mn.size()?-mx.top():mn.top()));
		}
		return;
	}
}
int main()
{
	//freopen("P1168_3.in","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

几道练习

P1801 黑匣子

link。

题意：和“中位数”类似。最开始的时候 Black Box（一个序列）是空的．而 $i=0$ 。要处理一串命令，命令只有两种：

ADD(x)：把 $x$ 元素放进 Black Box;
GET： $i$ 加 $1$ ，然后输出 Black Box 中第 $i$ 小的数。

对于 $100\%$ 的数据， $1 \leq n,m \leq 2 \times 10^{5},|a_i| \leq 2 \times 10^{9}$ ，保证 $u$ 序列单调不降。

题解：保证大根堆的元素个数为 $i$ ，其余按照“中位数”来做。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=200000+5;
	int n,m,a[N],b[N],index=0,q=1;
	priority_queue<int>mx,mn; 
	void yzmain()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		for(int i=1;i<=m;i++) scanf("%d",b+i);
		for(int i=1;i<=n;i++)
		{
			int tmp=a[i];
			if(mn.empty()||tmp>mn.top()) mx.push(-tmp);
			else mn.push(tmp);
			
			while(b[q]==i)
			{
				index++;
				while(mn.size()<=index&&mx.size()>0) mn.push(-mx.top()),mx.pop();
				while(mn.size()>index)               mx.push(-mn.top()),mn.pop();
				printf("%d\n",mn.top()),q++;
			}
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P7072 [CSP-J2020] 直播获奖

link。

题意：CCF 逐一评出每位选手（共 $n$ 位）的成绩，并直播即时的获奖分数线（当前排名前 $w\%$ 的选手的最低成绩就是即时的分数线）输出选手成绩逐一评出后，即时的获奖分数线（共输出 $n$ 次）。 $1\le n\le10^5$ 。

题解：保证小根堆的元素个数占总数的 $w\%$ ，其余按照“中位数”来做。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=100000+10;
	priority_queue<int>qmax,qmin;
	int n,w,a[N];
	void yzmain()
	{
		scanf("%d%d",&n,&w);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		for(int i=1;i<=n;i++)
		{
			if(qmin.empty() || -qmin.top()>a[i])
				qmax.push(a[i]);
			else qmin.push(-a[i]);
			while((qmin.size()*100<max(100,i*w)) && !qmax.empty())
				qmin.push(-qmax.top()),qmax.pop();
			while(qmax.size()*100<i*(100-w) && !qmin.empty())
				qmax.push(-qmin.top()),qmin.pop();
			printf("%d ",-qmin.top());
		}
	}	
}
int main()
{
	_yz::yzmain();
	return 0;
}

注意

千万不要将大根堆 / 小根堆弄混。

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/d9868096178d/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 堆对顶堆

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158