当前位置：首页 > news >正文

对顶堆

news 来源：原创 2024/5/7 16:47:39

对顶堆

所谓对顶堆，有点像双栈对顶那样，一个是小根堆，另一个是大根堆。假设 $g$ 是大根堆， $l$ 是小根堆，那么观察下图不难发现，两堆中间的元素，左边都是小于它的，且 $g . t o p ()$ 是小于它的最大值，右边都是大于它的，且 $l . t o p ()$ 是大于它的最小值
在这里插入图片描述

中位数问题

现在有一个序列动态输入，求每次输入后的中位数

利用上述对顶堆的思想，中位数肯定是中间的数，那么 $g$ 和 $l$ 维护的两个数就是动态输入时最中间的两个数，因此当两堆大小相等时，即输入序号为偶数时，中位数为二者的 $t o p ()$ 求和除以二；当两堆大小不相等时，即输入序号为奇数时，肯定有一个堆的的大小比另外一个堆大一，那么输出堆顶即可

注意

1.初始时两堆都为空，那么就随便选择一个堆进入

2.如果当前插入元素比大根堆的 $t o p ()$ ——即当前中位数左边的值小时，就插入到大根堆，同理在比小根堆 $t o p ()$ 大时插入到小根堆

3.如果输入序列为升序或者降序，不可能都插入到一个堆中，根据上述奇偶性，两堆大小要么差一要么相等，因此当一个堆大小比另外一个堆大 $2$ 及以上时，就对弹一下

因此我们得到如下函数：

priority_queue<double> g;
priority_queue<double, vector<double>, greater<double> > l;
int n;
double now;

void insert(int x) {   //必要时为double
    if(!g.size() || x < g.top()) g.push(x);  //条件放在一起判断并注意先后
    else l.push(x);
    //对弹
    if(g.size() > l.size() + 1) l.push(g.top()), g.pop();  //g.size() - l.size() > 1会运行错误
    if(l.size() > g.size() + 1) g.push(l.top()), l.pop();
}

POJ3784

对顶堆求中位数的裸题

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1e4 + 10;
priority_queue<int> g;
priority_queue<int, vector<int>, greater<int> > l;

void insert(int x) {
    if(!g.size() || x < g.top()) g.push(x);
    else l.push(x);
    if(g.size() > l.size() + 1) l.push(g.top()), g.pop();
    if(l.size() > g.size() + 1) g.push(l.top()), l.pop();
}

int main() {
    int t, n, x, kase, mid;
	scanf("%d", &t);
	while(t--) {
		while (g.size()) g.pop();
		while (l.size()) l.pop();
		scanf("%d%d", &kase, &n);
		printf("%d %d\n",kase, (n + 1) / 2);
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &x);
			insert(x);
			if (i & 1) {
				printf("%d ", g.size() > l.size() ? g.top() : l.top());
				if (++cnt == 10 && i != n) {
                    printf("\n");
                    cnt = 0;
                }
			}
		}
		printf("\n");
	}
	return 0;
}