[1655] 가운데를 말해요

### Priority Queue ###

[1655] 가운데를 말해요 : http://boj.kr/1655

<소스코드>

#include <cstdio>
#include <queue>
using namespace std;
 
int main()
{
    int n, k;
    scanf("%d", &n);
 
    priority_queue<int> minQ, maxQ;
    scanf("%d", &k);
    printf("%d\n", k);
    maxQ.push(k);
 
    for(int i=1; i<n; i++) {
        scanf("%d", &k);
        if(i&1) {
            if(maxQ.top() < k) minQ.push(-k);
            else {
                maxQ.push(k); minQ.push(-maxQ.top()); maxQ.pop();
            }
        }
        else {
            if(-minQ.top() > k) maxQ.push(k);
            else {
                minQ.push(-k); maxQ.push(-minQ.top()); minQ.pop();
            }
        }
        printf("%d\n", maxQ.top());
    }
    return 0; 
}

>> max Heap 과 min Heap 을 이용하여, 그때그때마다 중앙값을 알 수 있다.

- input : 1 5 2 10 -99 7 5 순이라면

1) max Heap : 1

   min Heap : empty

2) max Heap : 1

    min Heap : 5

3) max Heap : 1 2

    min Heap : 5

4) max Heap : 1 2

    min Heap : 5 10

5) max Heap : -99 1 2

    min Heap : 5 10

6) max Heap : -99 1 2

    min Heap : 5 7 10

이런식으로 진행이 된다. 그때그때 마다의 중앙값은 max Heap 의 루트가 된다.