Median of Stream: 두 힙으로 중앙값 유지

Median of Stream, 스트림 중앙값, running median

정의

스트림으로 들어오는 정수의 중앙값을 O(log N) 에 유지하는 문제.

두 힙 트릭

• Max-heap L: 아래 절반
• Min-heap R: 위 절반
• 크기 차 <= 1 유지, top(L) <= top(R) 유지

priority_queue<int> L;                              // max-heap
priority_queue<int, vector<int>, greater<>> R;      // min-heap

void add(int x) {
    if (L.empty() || x <= L.top()) L.push(x);
    else R.push(x);
    // 균형
    if (L.size() > R.size() + 1) { R.push(L.top()); L.pop(); }
    if (R.size() > L.size())     { L.push(R.top()); R.pop(); }
}

double median() {
    if (L.size() > R.size()) return L.top();
    return (L.top() + R.top()) / 2.0;
}

O(log N) per add, O(1) query.

참고

• Priority Queue / Heap
• Top K