Home 对顶堆的应用: AcWing 106 动态中位数
Post
Cancel

对顶堆的应用: AcWing 106 动态中位数

Link

每当数据集中有奇数个数据时, 就查询一次中位数. 可以想到用堆排序 (也即, 优先队列) 来做. 如果查询次数不是这么多的话, 其实还可以用树状数组.

我们都知道用优先队列可以“实时排序”, 但是优先队列是不能像数组那样「随机访问」的, 因此想要随时取出中位数就很麻烦, 需要 pop 出一半的数, 查完了还要 push 回去. 如果使用对顶堆, 事情就变简单了许多.

对于一个从小到大排序的有序数组, 我们将它从中间索引 mid 处划分成两半, 那么从 mid-1 到 1 就可以存入一个大顶堆, 从 mid 到 n 就可以存入一个小顶堆. 因此, 中位数就是小顶堆的 top, 我们需要做的只有实时维护大顶堆的对顶元素不能大于小顶堆的对顶元素, 且两个堆的大小之差不超过 1 即可.

这题还让我发现了一个从没注意过的问题: minHeap.size() 为 0 时, minHeap.size()-1 不是 -1, 而是 18446744073709551615! 这是啥啊? 64 位机能表示的最大数了吧? 也就是说, minHeap.size() 是一个无符号数啊… 看来以后不能随便减 1 了, 这么容易就溢出了. 一定要三思而后行.

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int p;
    scanf("%d",&p);
    for(int i=1;i<=p;++i){
        priority_queue<int>maxHeap; //默认是大根堆
        priority_queue<int,vector<int>,greater<int>>minHeap;
        int id,n,x,cnt=0;
        scanf("%d%d",&id,&n);
        printf("%d %d\n",id,(n+1)>>1);
        for(int j=1;j<=n;++j){
            scanf("%d",&x);
            maxHeap.push(x); //先放到大根堆里
            //调整使得大根堆中所有元素都小于小根堆中的元素
            //判断方法是:大根堆中最大的元素不能大于小根堆中最小的元素
            while(minHeap.size()&&maxHeap.top()>minHeap.top()){
                int a=maxHeap.top(),b=minHeap.top();
                maxHeap.pop(),minHeap.pop();
                maxHeap.push(b),minHeap.push(a);
            }
            //调整使得大根堆中的元素个数始终比小根堆中的元素少1个.这样做就可以保证小根堆的top就是中位数
            // cout<<minHeap.size()<<" "<<minHeap.size()-1<<endl;
            if(maxHeap.size()+1>minHeap.size()){
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            }
            if(j&1){
                printf("%d",minHeap.top());
                cnt++;
                if(j==n) printf("\n");
                else if(cnt==10){
                    cnt=0;
                    printf("\n");
                }else printf(" ");
            }
        }
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.