数据结构——对顶堆

对顶堆

由一个大根堆和一个小根堆组成，小根堆内里的数永远比大根堆内里的数要大
用途：用于动态维护区间内第k大的数，要比线段树和动态平衡树写起来更简单
 好比说我们要维护第k大的数，那么我们肯定是将前k大的数放进小根堆，小根堆的堆顶就是第k大的数
我们来看一下维护第k大的数的代码
1.建立大根堆和小根堆

1. priority_queue<int> qmax;  //相当于大顶堆
2. priority_queue<int,vector<int>,greater<int>> qmin;  //相当于小顶堆

复制代码

2.如果小根堆是空的，大概说当前元素大于小根堆的堆顶元素，那么就将当前元素存入小根堆，否则就存入大根堆 

1.                 if(qmin.empty()||a>=qmin.top())
2.                 {
3.                         qmin.push(a);
4.                 }
5.                 else
6.                 {
7.                         qmax.push(a);
8.                 }

复制代码

3.大、小根堆的维护，当我们小根堆的元素，不满k个，就将大根堆的堆顶元素弹入小根堆，如果我们当前小根堆的元素超过了k个，就将小根堆的堆顶元素摊入大根堆 

1.                 while(qmin.size()>k)
2.                 {
3.                         qmax.push(qmin.top());
4.                         qmin.pop();
5.                 }
6.                 while(qmin.size()<k&&!qmax.empty())
7.                 {
8.                         qmin.push(qmax.top());
9.                         qmax.pop();
10.                 }

复制代码

4.查询第k大的元素，访问小根堆的堆顶元素

1. cout<<qmin.top()<<"\n";

复制代码

 例题

P1168 中位数

思绪：去求奇数项的中位数，这个中位数的下标是在不断变化的，很板的一种动态维护第k大的元素的板题，直接套用对顶堆代码即可

1. #include<bits/stdc++.h>using namespace std;#define int long longint n,k;int a;priority_queue<int> qmax;priority_queue<int,vector<int>,greater<int> > qmin;signed main(){        cin>>n;        for(int i=1;i<=n;i++)        {                cin>>a;                if(i%2==1)                {                        k=(i+1)/2;                }                if(qmin.empty()||a>=qmin.top())
2.                 {
3.                         qmin.push(a);
4.                 }
5.                 else
6.                 {
7.                         qmax.push(a);
8.                 }                while(qmin.size()>k)
9.                 {
10.                         qmax.push(qmin.top());
11.                         qmin.pop();
12.                 }
13.                 while(qmin.size()<k&&!qmax.empty())
14.                 {
15.                         qmin.push(qmax.top());
16.                         qmax.pop();
17.                 }                if(i%2==1)                {                        cout<<qmin.top()<<"\n";                }        }        return 0;}

复制代码

 P7072 [CSP-J2020] 直播获奖

 思绪：第一眼看上去，获奖分数线为多少？即i*w/100位置上的人的分数是多少，翻译过来照旧第k大的元素是多少，动态维护第k大的对顶堆板题
直接写就行

1. #include<bits/stdc++.h>using namespace std;#define int long longint n,k;double w;int a;priority_queue<int>qmax;priority_queue<int,vector<int>,greater<int> >qmin;signed main(){        cin>>n>>w;        for(int i=1;i<=n;i++)        {                cin>>a;                 int z=floor(i*w/100);                k=max(1LL,z);                if(qmin.empty()||a>=qmin.top())
2.                 {
3.                         qmin.push(a);
4.                 }
5.                 else
6.                 {
7.                         qmax.push(a);
8.                 }                while(qmin.size()<k&&!qmax.empty())                {                        qmin.push(qmax.top());                        qmax.pop();                }                while(qmin.size()>k)                {                        qmax.push(qmin.top());                        qmin.pop();                }                cout<<qmin.top()<<" ";        }        return 0;}

复制代码

P2085 最小函数值

 思绪：我们发现a,b,c都是正数，那么其堆成周-b/2*a,永远都在负数的位置，也就是说，这n个函数，在0~正无穷内都是单调递增的，那么我们可以考虑一种剪枝的O(n*m)的写法，我们起首创建一个大顶堆，存储前k小的元素，我们在最外层遍历n个函数，内层遍历m个数，当n为1的时间，先将m个函数值存进去，然后当后续的函数，如果存在比堆顶元素小的，就存进大顶堆，弹出堆顶
,如果比堆顶元素大，那就立即竣事当前内层循环，由于后面也会比堆顶元素大，。
直到双重循环遍历完，然后输出倒序前m个即可

1. //P2085 最小函数值
2. #include<bits/stdc++.h>
3. using namespace std;
4. #define int long long
6. int n,m;
7. priority_queue<int>qmax;
8. int a,b,c;
9. int f;
10. int ans[200005];
11. signed main()
12. {
13.         cin>>n>>m;
14.         for(int i=1;i<=n;i++)
15.         {
16.                 cin>>a>>b>>c;
17.                 for(int j=1;j<=m;j++)
18.                 {
19.                         f=a*j*j+b*j+c;
20.                         if(i==1)
21.                         {
22.                                 qmax.push(f);
23.                         }
24.                         else
25.                         {
26.                                 if(f<qmax.top())
27.                                 {
28.                                         qmax.pop();
29.                                         qmax.push(f);
30.                                 }
31.                                 else
32.                                 {
33.                                         break;
34.                                 }
35.                         }
36.                 }
37.         }
38.         for(int i=1;i<=m;i++)
39.         {
40.                 ans[i]=qmax.top();
41.                 qmax.pop();
42.         }
43.         for(int i=m;i>=1;i--)
44.         {
45.                 cout<<ans[i]<<" ";
46.         }
47.         return 0;
48. }

复制代码

P1631 序列合并

思绪：和上面谁人一个思绪，我们写一个有剪枝的O(n^2)的写法 ，和上面谁人思绪差不多

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. int n;
5. int a[100005];
6. int b[100005];
7. int ans[100005];
8. priority_queue<int> q;
9. signed main()
10. {
11.         cin>>n;
12.         for(int i=1;i<=n;i++)
13.         cin>>a[i];
14.         for(int i=1;i<=n;i++)
15.         cin>>b[i];
16.         sort(a+1,a+1+n);
17.         sort(b+1,b+1+n);
18.         int k;
19.         for(int i=1;i<=n;i++)
20.         {
21.                 for(int j=1;j<=n;j++)
22.                 {
23.                         k=a[i]+b[j];
24.                         if(i==1)
25.                         {
26.                                 q.push(k);
27.                         }
28.                         else
29.                         {
30.                                 if(k<q.top())
31.                                 {
32.                                         q.pop();
33.                                         q.push(k);
34.                                 }
35.                                 else
36.                                 {
37.                                         break;
38.                                 }
39.                         }
40.                 }
41.         }
42.         for(int i=1;i<=n;i++)
43.         {
44.                 ans[i]+=q.top();
45.                 q.pop();
46.         }
47.         for(int i=n;i>=1;i--)
48.         cout<<ans[i]<<" ";
49.         return 0;
50. }

复制代码

P1801 黑匣子

思绪：我们很轻易发现，标题照旧动态求第k小的，因此我们要将前k小的，放入大根堆中，当我们大根堆位空，大概说当前元素小于大根堆的堆顶，就存进来，我们用vis去统计要举行输出的位置即可

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. int n,m;
5. int a[200005];
6. int b[200005];
7. int vis[200005];
8. priority_queue<int> qmax;
9. priority_queue<int,vector<int>,greater<int> > qmin;
11. signed main()
12. {
13.         cin>>n>>m;
14.         for(int i=1;i<=n;i++)
15.         {
16.                 cin>>a[i];
17.         }
18.         for(int i=1;i<=m;i++)
19.         {
20.                 cin>>b[i];
21.                 vis[b[i]]++;
22.         }
23.         int k=0;
24.         for(int i=1;i<=n;i++)
25.         {
26.                 if(qmax.empty()||a[i]<qmax.top())
27.         {
28.                 qmax.push(a[i]);
29.                 }
30.         else
31.         {
32.                 qmin.push(a[i]);
33.                 }
34.                 while(vis[i])
35.                 {
36.                         k++;
37.                         while(qmax.size()<k)
38.                         {
39.                                 qmax.push(qmin.top());
40.                                 qmin.pop();
41.                         }
42.                         while(qmax.size()>k)
43.                         {
44.                                 qmin.push(qmax.top());
45.                                 qmax.pop();
46.                         }
47.                         cout<<qmax.top()<<"\n";
48.                         vis[i]--;
49.                 }
50.         }
51.         return 0;
52. }

复制代码