对顶堆

发表于 | 分类于 | 浏览
字数统计: 923 | 阅读时长 ≈ 3

对顶堆

问题引入

有$n$个人依次入队，每个人的身高不同，当第$i$个人入队时询问$1\sim i$中身高第$k$小的人是谁

显然有一个$O(n^2)$的暴力算法，我们先将$n$个人的身高进行排序，并记录他们的入队次序，然后每次$O(n)$遍历找到$id$小于$i$的第$k$个人即可，但是当数据范围超过$1e^{5}$时该算法在时间上显然不能满足要求

如果你足够细心，你会发现该问题的本质是求区间内的第$k$小，那么我们可以考虑优秀的主席树，时间复杂度$O(nlog_{2}^{n})$，时间上可以满足要求，但是主席树的空间消耗极高，我们想尝试找到一个既节约时间又节约空间的算法

有没有这样的算法存在呢？

答案是有的

对顶堆概述

首先简单回顾一下什么是堆

堆分为大根堆和小根堆，堆的本质是一棵树，大根堆即树的根是这棵树上所有节点中最大的，并且任一节点的值大于其左右儿子节点，小根堆顾名思义，即为大根堆的相反结构

现在我定义一个大根堆$Max-Heap$，和一个小根堆$Min-Heap$，我们维护$Max-Heap$的大小为$k$，并且$Max-Heap$的堆顶元素小于或等于$Min-Heap$的堆顶元素，那么$Max-Heap$的堆顶即为所求区间中第$k$小的值

承接上例，我们现在要求$1\sim n$中的第$k$大，那么每当有人入队时，我们先将其放入$Max-Heap$中，假设放入之前其大小为$k-1$，那么现在其大小为$k$，我们将其堆顶元素取出，并放入$Min-Heap$中，然后将$Min-Heap$的堆顶元素取出并放入$Max-Heap$中，那么现在$Max-Heap$的堆顶即为所求的区间第$k$大，时间复杂度$O(nlog_{2}^{n})$，空间复杂度$O(n)$

例题：Running Median POJ - 3784

题目大意

给你一个长度$n$的数组，$n$保证为奇数，让你输出$1\sim n$中所有下标$i$为奇数时$1\sim i$的中位数

解题思路

显然就是让你求$1\sim i$中第$\frac{i+1}{2}$大的数，运用对顶堆实时处理即可

我们始终维护$Max-Heap$的堆顶元素为$1\sim i$中的中位数，那么$Max-Heap$的大小一定比$Min-Heap$大，并且正好大$1$，当$i$为偶数时，我们先将$a[i]$放入$Max-Heap$，然后取出$Max-Heap$的堆顶元素，并放入$Min-Heap$，这样，我们就保证了$Max-Heap$的堆顶为第$\frac{i}{2}$大的，当$i$为奇数时，我们将$a[i]$放入$Min-Heap$，然后将$Min-Heap$的堆顶元素取出并放入到$Max-Heap$中，这样，就保证了此时$Max-Heap$的堆顶为$1\sim i$中第$\frac{i+1}{2}$大的数

AC代码

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
#include <queue>
#include <iostream>
using namespace std;
priority_queue<long, vector<long> > max_que;
priority_queue<long, vector<long>, greater<long> > min_que;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T--) {
		int cas; cin >> cas;
		int n; cin >> n;
		cout << cas << ' ' << (n + 1) / 2 << '\n';
		while (!max_que.empty()) max_que.pop();
		while (!min_que.empty()) min_que.pop();
		for (int i = 1; i <= n; ++i) {
			long x; cin >> x;
			if ((i & 1) == 0) {
				max_que.push(x);
				min_que.push(max_que.top());
				max_que.pop();
			}
			else {
				min_que.push(x);
				max_que.push(min_que.top());
				min_que.pop();
				cout << max_que.top() << (((i + 1) >> 1) % 10 ? ' ' : '\n');
			}
		}
		cout << '\n';
	}
	return 0;
}