模板 - 对顶堆

发表于 更新于 分类于 ， 本文字数： 43 阅读时长 ≈ 1 分钟

一个大根堆一个小根堆怼一起，可以解决动态求中位数问题

Show code

UD_heap.hppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template <class _T>
class UD_heap {
private:
  std::priority_queue<_T> dq;
  std::priority_queue<_T, std::vector<_T>, std::greater<_T>> uq;
  bool _init = 0;

public:
  void clear() {
    _init = 0;
    dq = decltype(dq)();
    uq = decltype(uq)();
  }
  void init(_T x) {
    if (_init) {
      insert(x);
      return;
    }
    dq.push(x);
    _init = 1;
  }
  void insert(_T x) {
    if (!_init) {
      init(x);
      return;
    }
    (x > dq.top() ? uq.push(x) : dq.push(x));
    if (uq.size() > dq.size() + 1) {
      dq.push(uq.top());
      uq.pop();
    } else if (dq.size() > uq.size() + 1) {
      uq.push(dq.top());
      dq.pop();
    }
  }
  _T get_mid() { return uq.size() > dq.size() ? uq.top() : dq.top(); }
};