对顶堆 随笔

对顶推用二个堆实现，能够在nlog(n)的时间复杂度内找出，数组中第 K 小的元素。

把堆中的大根堆想成一个上宽下窄的三角形，把小根堆想成一个上窄下宽的三角形，那么对顶堆就可以具体地被想象成一个“陀螺”或者一个“沙漏”，通过这两个堆的上下组合，我们可以把一组数据分别加入到对顶堆中的大根堆和小根堆，以维护我们不同的需要。

priority_queue<int，vector<int>, less<int>> up;  //大根堆
priority_queue<int, vector<int>, greater<int> > down;//小顶推

我们需要维护这两个堆， 大根堆的堆顶元素 < 小根堆的堆顶元素，这样大根堆所有元素都小于小根堆的堆顶元素，另外我们维护小根堆的元素数量一定为K个， 那么 K的位置：

POJ 3784：
寻找中位数

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int main() {
	int P;
	cin >> P;
	while (P--) {
		int n, m,val;
		cin >> n >> m;
		cout << n << " " << (m + 1) / 2 << "\n";
		priority_queue<int, vector<int>, less<int> > up;  //大根堆
		priority_queue<int, vector<int>, greater<int> > down;//小根推
		int cnt = 0;
		for (int i = 1; i <= m; i++) {
			cin >> val;
			if (down.empty() || val > down.top()) down.push(val);
			else up.push(val);
			if (down.size() - 1 > up.size()) up.push(down.top()), down.pop();
			if (up.size() > down.size()) down.push(up.top()), up.pop();
			if (i % 2) {
				cnt++;
				cout << down.top() << " ";
				if (cnt % 10 == 0) cout << "\n";
			}
		}
		if (cnt % 10 ) cout << endl;
	}
}