对顶堆(动态维护中位数)

119 阅读 0 评论 79 点赞

我是靠谱客的博主呆萌棒球，这篇文章主要介绍对顶堆(动态维护中位数)，现在分享给大家，希望可以做个参考。

给定序列长度n，每输入奇数个数，求其中位数一次，最后输出所有中位数。

一道例题：poj:3784

分析：对顶堆做法，开两个堆，大根堆与小根堆，其中大根堆用来存排序后排名为1~n/2的数，小根堆用来存n/2+1~n的数。

那么维护好这两个堆，每次查询中位数只需要访问小根堆的堆顶即是中位数。

大根堆堆中的数字一定全部小于堆顶，小根堆堆中的数字一定全部大于等于堆顶，相当于排序后序列前一半的数字在大根堆，后一半在小根堆。

那么如何维护呢，我们需要解决两个问题：一是如何插入元素，向哪个堆插入；而是当某一个堆中的元素过多时，需要弹出元素，将其放入另一个堆中。

首先解决1：选择小根堆的堆顶元素作为分界点，比他小的元素都放到大根堆，比他大的放到小根堆。

其次解决2：:我们设q1,q2分别为大根堆，小根堆,n1,n2为大根堆元素个数，n2位小根堆元素个数，总元素个数为n。

那么不需要调整的情况：n2=n1+1;

2.1：当n1>n2时序列超过一半的元素在大根堆中，n2<floor(n*1.0/2)，那么此时排名在最中间的元素一定不在小根堆中，此时小根堆的堆顶元素不是中位数，故将大根堆的堆顶插入小根堆中。(参考序列 9 8 7 6 5 4)

2.2：当n2-n1==3时将小根堆堆顶插入大根堆，相当于平衡树失衡时的调整，(参考序列 1 2 3 4 5 6)。

上代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

//大根堆存放排名1~m/2的元素,小根堆存放排名为m/2+1~m的元素;
priority_queue<int>q1;//大根堆;
priority_queue<int,vector<int>,greater<int> >q2;//小根堆;
int fen;//分界点;
int n1,n2;//大根堆,小根堆的元素个数;
vector<int>v;//存结果;
void init(){
while(!q1.empty()) q1.pop();
while(!q2.empty()) q2.pop();
v.clear();
n1=0,n2=0;
fen=0;
}
void pushdown(){
int n;
scanf("%d",&n);
int x;
scanf("%d",&x);
fen=x;
q2.push(x);
v.push_back(x);
for(int i=2;i<=n;++i){
scanf("%d",&x);
if(x>=fen){
q2.push(x);
++n2;
}
else{
q1.push(x);
++n1;
}
/*----------调整----------*/
if(n1>n2){
fen=q1.top();
q1.pop();
q2.push(fen);
--n1;
++n2;
}
else if(n2-n1==3){
q1.push(q2.top());
++n1;
--n2;
q2.pop();
fen=q2.top();
}
if(i&1) v.push_back(q2.top());
}
}

当然，中位数还有另一种解法，即线段树做法，记录区间和，每次更新一次新加入的节点，在找一下区间第(i+1)/2大数就是中位数。

复制代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+7;
int a[maxn];
int b[maxn];
int m;
vector<int> v;
void init(int n){
sort(b,b+n);
m=unique(b,b+n)-b;
}
int getid(int x){
return lower_bound(b,b+m,x)-b;
}
int sum[maxn<<2|1];
void updata(int id,int l,int r,int k){
if(l==r){
++sum[k];
return ;
}
int mid=(l+r)>>1;
if(id<=mid) updata(id,l,mid,k<<1);
else updata(id,mid+1,r,k<<1|1);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
int myfind(int summ,int l,int r,int k){
if(l>r) return 0;
if(l==r) return l;
int mid=(l+r)>>1;
if(sum[k<<1]>=summ) return myfind(summ,l,mid,k<<1);
else return myfind(summ-sum[k<<1],mid+1,r,k<<1|1);
return 0;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
b[i]=a[i];
}
init(n);
for(int i=0;i<n;++i){
updata(getid(a[i]),0,m-1,1);
if(!(i&1)){
v.push_back(b[myfind((i+2)/2,0,m-1,1)]);
}
}
for(int i=0;i<v.size();++i)
printf("%dn",v[i]);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+7;
int a[maxn];
int b[maxn];
int m;
vector<int> v;
void init(int n){
sort(b,b+n);
m=unique(b,b+n)-b;
}
int getid(int x){
return lower_bound(b,b+m,x)-b;
}
int sum[maxn<<2|1];
void updata(int id,int l,int r,int k){
if(l==r){
++sum[k];
return ;
}
int mid=(l+r)>>1;
if(id<=mid) updata(id,l,mid,k<<1);
else updata(id,mid+1,r,k<<1|1);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
int myfind(int summ,int l,int r,int k){
if(l>r) return 0;
if(l==r) return l;
int mid=(l+r)>>1;
if(sum[k<<1]>=summ) return myfind(summ,l,mid,k<<1);
else return myfind(summ-sum[k<<1],mid+1,r,k<<1|1);
return 0;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
b[i]=a[i];
}
init(n);
for(int i=0;i<n;++i){
updata(getid(a[i]),0,m-1,1);
if(!(i&1)){
v.push_back(b[myfind((i+2)/2,0,m-1,1)]);
}
}
for(int i=0;i<v.size();++i)
printf("%dn",v[i]);
return 0;
}