边输入边排序（二分插入）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
vector<int> a;
int main(int argc, char **argv){
	cin >> n;
	for (int i = 1;i <= n;i++){
		int x;
		cin >> x;
		auto it = lower_bound(a.begin(),a.end(),x);
		a.emplace(it,x);
		// for (int j = 0;j < a.size();j++){
		// 	cout << a[j] << " ";
		// }
		// cout << endl;
		if (i & 1){
			cout << a[(i >> 1)] << endl;
		}
	}
	return 0;
}

对顶堆写法（这个偏过程，简洁版看这里）

#include <bits/stdc++.h>
using namespace std;
template<typename tp>
class Heap{
	private:
		vector<tp> hp = {0};
		bool (*cmp)(tp,tp);
		void down(int p){
			int n = size();
			while (p << 1 <= n){
				int t = p << 1;
				if (t < n && (*cmp)(hp[t + 1],hp[t])) t++;
				if ((*cmp)(hp[t],hp[p])){
					swap(hp[t],hp[p]);
					p = t;
				}else	break;
			}
		}
		void up(int p){
			while (p > 1 && (*cmp)(hp[p],hp[p >> 1])){
				swap(hp[p],hp[p >> 1]);
				p >>= 1;
			}
		}
		tp get(int p){
			return hp[p];
		}
	public:
		Heap(){
			cmp = [](tp a,tp b){return a > b;};
		}
		Heap(bool (*f)(tp,tp)){
			cmp = f;
		}
		int size(){
			return hp.size() - 1;
		}
		void ins(tp x){
			hp.emplace_back(x);
			up(size());
		}
		void rm(int p){
			swap(hp[p],hp[size()]);
			hp.pop_back();
			down(p);
		}
		void pop(){
			rm(1);
		}
		tp top(){
			return get(1);
		}
		tp operator[](int p){
			return get(p);
		}
};

bool cmp(int a,int b){
	return a < b;
}
Heap<int> hb,hs(cmp);
int main(int argc, char **argv){
	int n;
	cin >> n;
	int x;
	cin >> x;
	hs.ins(x);
	printf("%d\n",x);
	for (int i = 2;i <= n;i++){
		cin >> x;
		if (hs.size() == hb.size()){
			if (x >= hb.top())	hs.ins(x);
			else{
				hs.ins(hb.top());
				hb.pop();
				hb.ins(x);
			}
		}
		else{
			if (x <= hs.top())	hb.ins(x);
			else{
				hb.ins(hs.top());
				hs.pop();
				hs.ins(x);
			}
		}
		if (i & 1)	printf("%d\n",hs.top());
	}
	return 0;
}

更简洁的中位对顶堆写法

#include<bits/stdc++.h>
using namespace std;
template<typename T>
class d_heap
{
	private:
		#define pq priority_queue
		pq<T>big;
		pq<T,vector<T>,greater<T> >small;
		#undef pq
		void ph()//左右平衡 
		{
			if(big.size()<small.size())
				big.push(small.top()),small.pop();
			if(big.size()-small.size()>1)
				small.push(big.top()),big.pop();
		}
	public:
		void push(T x)
		{
			if(small.size() && x>small.top())small.push(x);
			else big.push(x);
			ph();
		}
		T top()
		{
			return big.top();
		}
};
d_heap<int>q;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		q.push(x);
		if(i%2)
			cout<<q.top()<<"\n";
	}
	return 0;
}

vector+二分写法

#include<bits/stdc++.h>
using namespace std;
vector<int>v;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		v.insert(upper_bound(v.begin(),v.end(),x),x);
		if(i%2)
			cout<<v[v.size()/2]<<"\n";
	}
	return 0;
}