堆

二叉堆

void solve() {
  int n;
  cin >> n;
  vector<int> a(n + 10);
  int cnt = 0;
  function<void(int)> pushup = [&](int u) {
    if (u == 1) {
      return;
    }
    int fa = u >> 1;
    if (a[u] < a[fa]) {
      swap(a[u], a[fa]);
      pushup(fa);
    }
  };
  function<void(int)> pushdown = [&](int u) {
    int v = u << 1;
    if (v > cnt) {
      return;
    }
    if ((v | 1) <= cnt && a[v | 1] < a[v]) {
      v |= 1;
    }
    if (a[v] < a[u]) {
      swap(a[v], a[u]);
      pushdown(v);
    }
  };
  auto push = [&](int x) {
    a[++cnt] = x;
    pushup(cnt);
  };
  auto pop = [&]() {
    a[1] = a[cnt--];
    pushdown(1);
  };
  for (int i = 1; i <= n; ++i) {
    int q;
    cin >> q;
    if (q == 1) {
      int x;
      cin >> x;
      push(x);
    } else if (q == 2) {
      cout << a[1] << endl;
    } else {
      pop();
    }
  }
}

对顶堆

SPOJ-RMID2 Luogu-SP16254

多组数据，不断读入整数，读入到 $-1$ 时输出并删除当前序列中位数（$-1$ 不插入），偶数个数时输出较小的中位数，遇到 $0$ 结束。

数据范围 $10^5$。

void solve() {
  int x;
  priority_queue<int> lq;
  priority_queue<int, vector<int>, greater<int>> rq;
  // 调整对顶堆
  auto adjust = [&](int sz) {
    while (lq.size() < sz && !rq.empty()) {
      lq.push(rq.top());
      rq.pop();
    }
    while (lq.size() > sz) {
      rq.push(lq.top());
      lq.pop();
    }
  };
  // 插入新元素
  auto push = [&](int x) {
    if (lq.empty() || x < lq.top()) {
      lq.push(x);
    } else {
      rq.push(x);
    }
    int mid = (lq.size() + rq.size() + 1) / 2;
    adjust(mid);
  };
  auto pop = [&]() {
    lq.pop();
    int mid = (lq.size() + rq.size() + 1) / 2;
    adjust(mid);
  };
  while (scanf("%d", &x) != EOF) {
    if (x == 0) {
      return;
    }
    if (x == -1) {
      printf("%d\n", lq.top());
      pop();
    } else {
      push(x);
    }
  }
}