【笔记】对顶堆

Part 1 简介

对顶堆是一种可以 $O(\log n)$ 维护在线第K小值的数据结构

其实就是一个大根堆和一个小根堆啦

Part 2 例题

Luogu P1168 中位数

Luogu P3871 [TJOI2010]中位数

Part 3 代码实现

/*
 * @Author: thyzzs
 * @Date: 2019-09-08 16:52:21
 * @LastEditTime: 2019-11-13 18:11:57
 */
struct Double_Heap {
    priority_queue<int> minq;  //存放最小的若干个数的大根堆
    priority_queue<int, vector<int>, greater<int>> maxq;  //存放最大的若干个数的小根堆
    //对顶堆动态维护一段只能添加的序列，寻找其中的第k大值
    //需要的元素维持在minq的堆顶

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

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