---
# System prepended metadata

title: 使用 priority queue 更新中位數
tags: [STL]

---

# 使用 priority queue 更新中位數
###### tags: `STL`
**將數據流分成兩半 一半大 一半小**
```
#include </Users/lochieh/Desktop/Uva/bits/stdc++.h>
int main(int argc, char const *argv[])
{
	std::priority_queue<int, std::vector<int>, std::greater<int> > Mh;
	std::priority_queue<int> mh;
	int i;
	while(std::cin >> i) {
		if(mh.empty() || i < mh.top()) mh.emplace(i);
		else Mh.emplace(i);

		if(mh.size() > Mh.size() + 1) {
			Mh.emplace(mh.top());
			mh.pop();
		}else if(mh.size() + 1 < Mh.size()) {
			mh.emplace(Mh.top());
			Mh.pop();
		}
        
		if(Mh.size() == mh.size()) std::cout << (Mh.top() + mh.top()) / 2 << "\n";
		else if(Mh.size() > mh.size()) std::cout << Mh.top() << "\n";
		else std::cout << mh.top() << "\n";
	}
	return 0;
}
```