不竭尽全力去做一件事,你永远不知道,你会有多优秀,加油

对顶堆

定义 :

其实就是两个堆,讲一个堆倒过来,让其看一看成一个堆的排序
借用一下图形就是这样子的

如果上面是大根堆下面是小根堆的话,整体来说就是小跟堆
反过来 上面是小根堆下面是大根堆的话,整体就是大根堆;

用途:

我目前知道的就是不断地找到第几大,第几小,就是求得是个变化的值;慢慢发掘吧。

先举个栗子吧:
P1801 黑匣子
一道对顶堆的题
具体题意看原题吧,我就简单的说一下题意

这样做的时间复杂度是O(nlogn)的

就是分别找一定的范围找 第几小的值;
这样的话我们会发现有两个变量,在不停的变化,我们不好用一个堆来解决问题,因为如果你用一个堆的话 第几小这个问题可以解决但是问题是你得在一定范围内找出第几小,范围不一样,排出的序 也就不尽相等,除非原序列本身就是单调的,而且跟我要的顺序是一致的,这是不可能的。
所以我们用对顶堆,<mark>两个堆的作用 整体是进行排序的,其中一个是记录第几大的。</mark>

可以按照这种理解:
所以对于addadd操作,我们先将元素放入下面的大根堆内,从堆顶不断取出元素放到小根堆直到大根堆元素个数为ii,这样大根堆的根就是第i小的元素,同时可以保证对顶堆的性质
同理,对于getget操作,我们先输出大根堆的根,然后将小根堆的根移到大根堆(因为i每次加一,要始终保证大根堆有i个元素),这样仍保证对顶堆的性质不变

对于这个题(对顶堆)我自己的理解,(我感觉这样想会更好理解); 不好意思下面那段文字写的太多,忘调整了,我啰嗦一下吧。 就是挡板上面的是我们维护的小根堆,下面是我们维护的大根堆,我们先不看挡板,就是这一个整体是从上到下,从大到小的也就是大根堆, 这样我们可以看出挡板上面维护的堆,堆顶就是我们要找的第几小的那个数,所以我们就把问题转换成移动挡板的位置,当然是在不断地扩大范围的基础上,(做个题一个前提就是要求的序列是单调递增的);


两种代码;
其实差不多,自己看着那种好理解,就用那种吧

一:

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <queue>
#include <bits/stdc++.h>
#define ll long long int
#define sc(a) scanf("%lld",&a)
#pragma GCC optimize(2)
const int MOD=1e9+7;
const int maxn=2e5+7;
using namespace std;
const int mod=998244353;
const int dx[7]={-1, 0, 0, 1, 1, 1};//奇数行 
const int dy[7]={0 , 1,-1, 1, 0,-1};
const int dx1[7]={-1, -1, -1, 0, 0, 1};//偶数行 
const int dy1[7]={-1,  1,  0, 1,-1, 0};

priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小 

ll n,t,l,m,k,sum,cnt,ans,num;
ll a[maxn],b[maxn];
ll dp[1010][1010],dis[maxn];
char str[maxn],s[maxn];

int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		scanf("%lld",&a[i]);
	l=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&ans);
		for(int j=l;j<=ans;j++){
			mx.push(a[j]);
			if(mx.size()==i) mn.push(mx.top()),mx.pop();
		}	
		l=ans+1;
		printf("%lld\n",mn.top());
		mx.push(mn.top());
		mn.pop();
	}
	return 0;
} 

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <queue>
#include <bits/stdc++.h>
#define ll long long int
#define sc(a) scanf("%lld",&a)
#pragma GCC optimize(2)
const int MOD=1e9+7;
const int maxn=2e5+7;
using namespace std;
const int mod=998244353;
const int dx[7]={-1, 0, 0, 1, 1, 1};//奇数行 
const int dy[7]={0 , 1,-1, 1, 0,-1};
const int dx1[7]={-1, -1, -1, 0, 0, 1};//偶数行 
const int dy1[7]={-1,  1,  0, 1,-1, 0};

priority_queue<ll , vector<ll> , greater<ll> > mn;
priority_queue<ll , vector<ll> , less<ll> > mx;

ll n,t,m,k,sum,cnt,ans,num;
ll a[maxn],b[maxn];
ll dp[1010][1010],dis[maxn];
char str[maxn],s[maxn];

int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&b[i]),dis[b[i]]++;;
	for(int i=1;i<=m;i++)
	{
		mx.push(a[i]);
		if(mx.size()>num){
			mn.push(mx.top());
			mx.pop();
		}
		while(dis[i]){
			printf("%lld\n",mn.top());
			mx.push(mn.top());
			mn.pop();
			num++;
			dis[i]--;
		}
	}
	
	return 0;
}