DataStructure/Median.cpp

Back to top page

• category: DataStructure
• View this file on GitHub
  • Last commit date: 2020-04-27 12:42:37+09:00

Description

集合の中央値を管理する。
push(x) : 集合に x を追加する。 O(log N)
get() : 集合の中央値を返す。 O(1)

Code

//@docs Docs/Median.md
template <class T>
struct Median {
    priority_queue<T> smq;
    priority_queue<T, vector<T>, greater<T>> lgq;
    void push(T x) {
        if (smq.empty()) {
            smq.push(x);
            return;
        }
        T t = smq.top();
        if (smq.size() > lgq.size()) {
            if (t <= x) {
                lgq.push(x);
            } else {
                lgq.push(t);
                smq.pop();
                smq.push(x);
            }
        } else {
            if (t >= x) {
                smq.push(x);
            } else {
                lgq.push(x);
                smq.push(lgq.top());
                lgq.pop();
            }
        }
    }
    inline T get() { return smq.top(); }
};

#line 1 "DataStructure/Median.cpp"
//@docs Docs/Median.md
template <class T>
struct Median {
    priority_queue<T> smq;
    priority_queue<T, vector<T>, greater<T>> lgq;
    void push(T x) {
        if (smq.empty()) {
            smq.push(x);
            return;
        }
        T t = smq.top();
        if (smq.size() > lgq.size()) {
            if (t <= x) {
                lgq.push(x);
            } else {
                lgq.push(t);
                smq.pop();
                smq.push(x);
            }
        } else {
            if (t >= x) {
                smq.push(x);
            } else {
                lgq.push(x);
                smq.push(lgq.top());
                lgq.pop();
            }
        }
    }
    inline T get() { return smq.top(); }
};

Back to top page