对顶堆学习笔记

· · 个人记录

什么是对顶堆？

所谓对顶堆，就是将一个小顶堆和一个大顶堆按照需要叠合起来，一般来说，有这样两种情况：

他有什么用呢？

一言以蔽之，就是动态维护一个数列中第 k 小 或 第 k 大的数

当然对于这个问题也可以用桶排序解决，但是对顶堆可以处理相比于桶排序而言数据量更大的题目，并且在有的情况它可以完成桶排序解决不了的问题

如何实现

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

反之亦然，当我们把大顶堆放在小顶堆上面时（上图第一种情况） 那么如果小顶堆的堆顶元素比大顶堆的堆顶元素要小，那么大顶堆的所有元素都要比小顶堆的元素大。

回到这个问题：对于第二种情况，我们要求第 k 小的元素，那么我们把大根堆的元素个数限制成K个，前K个元素入队之后，每个元素在入队之前先与堆顶元素比较，如果比堆顶元素大，就加入小根堆，如果没有的话，把大根堆的堆顶弹出，将新元素加入大根堆。这样就维护出一个对顶堆。它的作用在于找出第K小的元素。

代码实现

建堆

priority_queue<int>max_dui;
priority_queue<int,vector<int>,greater<int> >min_dui;

插入数

void push(int x){
    if(x>max_dui.top()){
    min_dui.push(x);
    }
    else max_dui.push(x);
    tiao();
}

调整堆的数量（维护在 k 的范围内）

void tiao(){
    if(min_dui.size()<now){
        min_dui.push(max_dui.top());
        max_dui.pop();
    }
    if(min_dui.size()>now){
        max_dui.push(min_dui.top());
        min_dui.pop();
    }
}

例题

P7072 [CSP-J2020] 直播获奖

题目大意：每次插入一个数，求数列中第 k 大的数

使用对顶堆，维护数列中第 k 大的数

代码：

#include<iostream>
#include<queue>
using namespace std;
int n,w,now,num;
priority_queue<int>max_dui;
priority_queue<int,vector<int>,greater<int> >min_dui;
void tiao(){
    if(min_dui.size()<now){
        min_dui.push(max_dui.top());
        max_dui.pop();
    }
    if(min_dui.size()>now){
        max_dui.push(min_dui.top());
        min_dui.pop();
    }
}
void push(int x){
    if(x>max_dui.top()){
    min_dui.push(x);
    }
    else max_dui.push(x);
    tiao();
}
int main(){
    cin>>n>>w;
    max_dui.push(0);
    for(int i=1;i<=n;i++){
        now=max(1,i*w/100);
        cin>>num;
        push(num);
        cout<<min_dui.top()<<" ";
    }
}

~~ 未完待续