UESTC 1063秋実兄貴と妹紙二叉堆(大根樹)

秋実兄貴と妹紙
Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 1500/1500KB (Java/Others)
Submit  Status
中和、天地位焉、万物育焉.秋実兄貴は中庸を追求する人だ.
秋実兄貴の憧れは多いが、秋実兄貴は極端な妹紙が好きではない.だから彼は自分を慕うすべての妹紙の中から中庸の道に合ったものを選びたいと思っています.
各妹紙の秋実兄貴への憧れの程度は整数aiで表すことができ、秋実兄貴はこれらの数の中位数を見つけようとしている.
有限個数のデータの中央値を計算する方法は、次のとおりです.

                 。          ，                 ；
          ，    2                   。

Input
1行目には整数nがあり、秋実兄貴の憧れの数を表す.
次にn行、各行に正の整数aiがあります.
1≤n≤250000 , 1≤ai<231 .
Output
このn個の数の中位数を出力し、小数を1桁保持します.
Sample input and output
Sample Input
Sample Output

3
1
2
3

2.0

Hint
メモリサイズの制限に注意してください.
Source
2015 UESTC Training for Data Structures
The question is from here.
My Solution
 Memory Limit: 1500/1500KB (Java/Others)
カードメモリのタイトル、初めて出会った
n/2+1個の要素を維持すればいい、後ろのpush、pop
本来はC++STLのpriority_queueは1つ書いて、結局メモリを爆発させて、MLE
だから二叉の山で書きます

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 125001;

int heap[maxn],  sz = 1;

void up(int i) {
    int x = heap[i];

    for(int j = i/2; j >= 1; j/=2) {            //        i ，  WA2    WA1，    test2       bug ☺
        if(heap[j] > x){
            heap[i] = heap[j];
            i = j;
        } else {
            break;
        }
    }
    heap[i] = x;
}
void down(int i) {
    int x = heap[i];

    for(int j = i*2; j <= sz; j*=2){
        j += j < sz&& heap[j] > heap[j+1];
        if(heap[j] < x){
            heap[i] = heap[j];
            i = j;
        } else {
            break;
        }
    }
    heap[i] = x;
}
void push(int v) {
    heap[++sz] = v;
    up(sz);
}
void pop() {
    swap(heap[1], heap[sz]);
    sz--;
    down(1);
}
int top() {
    return heap[1];
}

int main()
{
    int n, a;
    scanf("%d", &n);
    for(int i = 0; i < n/2 +1; i++){
        scanf("%d", &a);push(a);
    }
    for(int i = n/2 +1; i < n; i++){
        scanf("%d", &a);
        push(a);pop();
    }
    pop();
    if(n % 2 ==1) printf("%.1f", (double)heap[1]);
    else{
        a = top();pop();
        printf("%.1f", (double)a/2+(double)top()/2);
    }
    return 0;
}

thank you!