对顶堆

洛谷 1168 中位数

题目描述

给出一个长度为NN的非负整数序列A_iAi​，对于所有1≤k≤(N+1)/2，输出A1​,A3​,…,A2k−1​的中位数。即前1,3,5,…个数的中位数。

输入格式

第1行为一个正整数N，表示了序列长度。

第2行包含N个非负整数Ai​(Ai​≤10^9)。

输出格式

共(N+1)/2行，第i行为A1​,A3​,…,A2k−1​的中位数。

输入输出样例

输入 

7
1 3 5 7 9 11 6

输出 

1
3
5
6

说明/提示

对于20\%20%的数据，N ≤ 100N≤100；

对于40\%40%的数据，N ≤ 3000N≤3000；

对于100\%100%的数据，N ≤ 100000N≤100000。

解析：

使用两个堆，大根堆维护较小的值，小根堆维护较大的值，即大根堆的堆顶是较小的数中最大的，小根堆的堆顶是较大的数中最小的

将大于大根堆堆顶的数（比所有大根堆中的元素都大）的数放入小根堆，小于等于大根堆堆顶的数（比所有小根堆中的元素都小）的数放入大根堆，那么就保证了所有大根堆中的元素都小于小根堆中的元素

于是我们发现对于大根堆的堆顶元素，有【小根堆的元素个数】个元素比该元素大，【大根堆的元素个数-1】个元素比该元素小；同理，对于小跟堆的堆顶元素，有【大根堆的元素个数】个元素比该元素小，【小根堆的元素个数-1】个元素比该元素大；

那么维护【大根堆的元素个数】和【小根堆的元素个数】差值不大于1之后，元素个数较多的堆的堆顶元素即为当前中位数；（如果元素个数相同，那么就是两个堆堆顶元素的平均数，本题不会出现这种情况）

根据这两个堆的定义，维护方式也很简单，把元素个数多的堆的堆顶元素取出，放入元素个数少的堆即可

AC代码：

#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int> >Q1;//大根堆，维护较小的数值
priority_queue<int,vector<int>,greater<int> >Q2;//小根堆，维护较大的数值
int main(){
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(!Q1.empty()&&x<=Q1.top()) Q1.push(x);
        else if(!Q2.empty()&&x>Q2.top()) Q2.push(x);
        else Q2.push(x);
        //调整堆的大小，满足（小顶堆元素个数）-（大顶堆元素个数）= 1
        if(Q1.size()>Q2.size()){
            Q2.push(Q1.top());
            Q1.pop();
        }
        else if(Q2.size()>Q1.size()+1){
            Q1.push(Q2.top());
            Q2.pop();
        }
        if(i%2==1) printf("%d\n",Q2.top());
    }    
    return 0;
}