对顶堆的理解与使用(直播获奖,中位数)

简介: 对顶堆的理解与使用(直播获奖,中位数)

1.前言


在今天的做题过程中遇见了这样一类问题:

动态维护n个数中的 第k大的数 / 第k小的数 / 中位数

一开始没有什么思路,然后尝试每加入一个数用一次sort然后输出所要求的的数,不出意外爆掉了,在补题的时候看到了对顶堆这种非常优秀的数据结构,所以 学完写一篇博客,持续更新;


2.实现原理


我们用STL中的 单调队列大根堆和小根堆来实现对顶堆;


对顶堆由一个小根堆和一个大根堆组成,维护小根堆堆顶为第 k 大的元素,大于它的放在小根堆,小于它的放入大根堆


priority_queue< int > maxp;//大根堆

priority_queue<int,vector< int >,greater< int > >minp;//小根堆


在小根堆里维护小根堆堆顶为 第 k 大个元素

(维护中位数是维护第 k 大个元素的一个特例,维护第 k 小个元素即是维护第(n-k)大个元素)


4d69715935d7fc16a7ac1d259b5bef05_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBALkFzaHku,size_20,color_FFFFFF,t_70,g_se,x_16.png


1.元素的插入:


当我们有一个元素之后,我们是选择放入大根堆还是放入小根堆呢,我们在这里把小根堆堆顶作为一个标志(后面的实现会给出用大根堆堆顶做标志的不方便之处),大于它的放入小根堆,否则放入大根堆,等于它的放在哪里都可,因为对后面维护没影响,这样插入就保证了整个对顶堆的数据整体的有序性,一开始把第一个元素作为标志元素,方便维护;


void push(int num)
{
  if(num>=minp.top())//小根堆堆顶做标志
  minp.push(num);
  else 
  maxp.push(num);
  trans();//每插入一个数据维护一次
}


2.元素的维护:


每次放入一个元素后我们都要做一次维护,维护很简单,因为整体元素已经有序,我们只要保证小根堆中的元素恰好为 k 个即可。少元素在大根堆堆顶取出,否则把自己堆顶元素放入大根堆


void trans()
{
  while(minp.size()<now)//now为k,即要维护的第k大,不够就去大根堆中取
  {
  minp.push(maxp.top());
  maxp.pop();
  } 
  while(minp.size()>now)//多了就往大根堆放
  {
  maxp.push(minp.top());
  minp.pop();
  }
}


3.例题


1.洛谷P7072 直播获奖

题目大意:

根据题中给出人数与分数线的关系动态维护第 k 大的元素;


priority_queue<int> maxp;
priority_queue<int,vector<int>,greater<int>>minp;
int n,w,now,num;
void trans()//维护
{
  while(minp.size()<now)
  {
  minp.push(maxp.top());
  maxp.pop();
  } 
  while(minp.size()>now)
  {
  maxp.push(minp.top());
  minp.pop();
  }
} 
void push(int num)//插入
{
  if(num>=minp.top())
  minp.push(num);
  else 
  maxp.push(num);
  trans();
}
int main()
{
  scanf("%d %d",&n,&w);
  scanf("%d",&num);
  minp.push(num);
  printf("%d ",minp.top());//把第一个元素放在小根堆堆顶做标志元素,同时根据题意,当只有一个元素时第一个元素一定是分数线
  for (int p=2;p<=n;p++)
  {
  now=max(1,p*w/100);//整除就是小数的向下取整,不会出现误差
  scanf("%d",&num);
  push(num);
  printf("%d ",minp.top()); 
  }
  return 0;
}



2.洛谷P3871 中位数

题目大意:

动态维护中位数

根据题意,无论我们要维护的数总数为奇还是为偶

我们要的 k 总为( n / 2 ) + 1;


priority_queue<ll>maxq;
priority_queue<ll,vector<ll>,greater<ll>>minq;
ll n;
ll num,now;
ll m,cnt;
string s; 
void trans()//维护
{
  while(minq.size()>now)
  {
  maxq.push(minq.top());
  minq.pop();
  }
  while(minq.size()<now)
  {
  minq.push(maxq.top());
  maxq.pop();
  }
}
void push(int num)//插入
{
  if(num>=minq.top())
  minq.push(num);
  else
  maxq.push(num);
  trans();
}
int main()
{
  cin>>n;
  scanf("%lld",&num);
  minq.push(num);// n 必然大于 0 ,因此我们把第一个数作为标志元素
  for(int i=2;i<=n;i++)
  {
  scanf("%lld",&num);
  now=i/2+1;
  push(num);
  }//把 n 个元素插入并维护
  cin>>m;
  for(int i=1;i<=m;i++)
  {
  cin>>s;
  if(s=="add")
  {
    cnt++;
    now=(cnt+n)/2+1;
    scanf("%lld",&num);
    push(num);//记录新插入元素的个数,并维护对顶堆
  }
  else
  {
    printf("%lld\n",minq.top());//维护的小根堆的堆顶即为中位数
  }
  }
  return 0; 
}



这里我们给出用大根堆堆顶作为标志的不方便之处

假如 n = 1;然后不插入直接查询,我们让大根堆堆顶作为标志的话,小根堆是空的最后还要特判,不如直接使用小根堆堆顶做插入标志方便,同时小根堆堆顶还是最后维护的值,比较好记;


4.拓展


当遇到不是动态维护第 k 大元素的时候,而仅仅是求一个无规则数列中的第 k 大的数时,我们可以借助STL中的 nth_element这个函数来实现


nth_element的作用是求第 k 小的元素,我们稍加改造就能求第 k 大的元素

它会使第 k 小的元素归位,使它前边的元素小于它,使它后面的元素大于它;

它的用法是

nth_element(a+x,a+x+y,a+x+len);


能使下标从 x 到 x+y-1 的元素小于 x+y 
          从 x+y+1 到 x+y+len 的元素大于 x+y;


时间复杂度只有 O(n),十分好用


例题链接 洛谷P1923 求第k小的数


本人是新手,有什么错误欢迎指出~


目录
相关文章
|
10月前
【每日一题Day361】LC2558从数量最多的堆取走礼物 | 大顶堆
【每日一题Day361】LC2558从数量最多的堆取走礼物 | 大顶堆
52 0
|
10月前
剑指 Offer 60:n个骰子的点数
剑指 Offer 60:n个骰子的点数
62 0
【刷穿 LeetCode】剑指 Offer II 069. 山峰数组的顶部 : 二分 & 三分极值问题
【刷穿 LeetCode】剑指 Offer II 069. 山峰数组的顶部 : 二分 & 三分极值问题
|
Java C++
LeetCode(剑指 Offer)- 60. n个骰子的点数
LeetCode(剑指 Offer)- 60. n个骰子的点数
106 0
LeetCode(剑指 Offer)- 60. n个骰子的点数
|
数据安全/隐私保护
AcWing 第 20 场周赛 3995. 最小的和(贪心 优先队列)
AcWing 第 20 场周赛 3995. 最小的和(贪心 优先队列)
141 0
AcWing 第 20 场周赛 3995. 最小的和(贪心 优先队列)