[笔记]对顶堆

简介

对顶堆是一种可以 $O(\textrm{log},n)$ 在线维护第 k 大值的数据结构(大雾

对顶堆动态维护一段只能添加的序列,寻找其中的第 k 大值

代码实现

只需要一个类啦

 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
/*
 * @Author: lhw
 * @Date: 2019-11-27 19:34:44
 * @LastEditTime: 2019-11-28 15:12:55
 */

class Double_Heap {
    priority_queue<int> minh;  	//存放最小的若干个数的大根堆
    priority_queue<int, vector<int>, greater<int> > maxh;	//存放最大的若干个数的小根堆

    //需要的元素维持在minh的堆顶

    void insert(int n) {
        if (!minh.empty() && n > maxh.top()) {  //若n比maxh最小的要大,则交换n与maxh.top()
            maxh.push(n);
            n = maxh.top();
            maxh.pop();
        }
        minh.push(n);  //n插入小根堆
    }

    int find_kth(int k) {  	//寻找第k大数
        while (minh.size() > k) {  	//minh元素过多,插进maxh
            maxh.push(minh.top());
            minh.pop();
        }
        while (minh.size() < k) {  	//minh元素过少,从maxh插回来
            minh.push(maxh.top());
            maxh.pop();
        }
        return minh.top();
    }
}

同理也可以实现在线维护第 k 小

例题

Luogu P1168 中位数

Luogu P3871 中位数(TJOI2010)

updatedupdated2020-03-272020-03-27
Update Site @2020-03-27-15:18:47
加载评论
点击刷新