对顶堆解法：

算法原理

使用一个大根堆维护较小的一半数

使用一个小根堆维护较大的一半数

保持两个堆的大小差不超过1

中位数总是位于堆顶

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    // 大根堆维护较小的一半数
    priority_queue<int>max_heap;
    // 小根堆维护较大的一半数
    priority_queue<int,vector<int>,greater<int>>min_heap;
    for (int i=1;i<=n;i++){
        int x;
        cin>>x;
        
        // 插入策略
        if(max_heap.empty()||x<=max_heap.top()){
            max_heap.push(x);
        }else{
            min_heap.push(x);
        }
        
        // 平衡堆大小
		if (max_heap.size()>min_heap.size()+1){
            min_heap.push(max_heap.top());
            max_heap.pop();
        }else if(min_heap.size()>max_heap.size()){
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
        
        // 输出奇数长度的中位数
        if(i%2==1){
            cout << max_heap.top()<<endl;
        }
    }
    return 0;
}