[BOJ] 2696번: 중앙값 구하기

https://www.acmicpc.net/problem/2696

segment tree를 가지고 해결해도 되지만, 중앙값 이하의 값들을 담아두는 max heap과 초과의 값들을 담아두는 min heap을 가지고 해결할수도 있습니다. 23 41 13 22 65를 가지고 heap을 구성해본다면

<23>
max heap : 23

min heap : x (max heap의 top인 23을 출력)

<23 41>

max heap : 23

min heap : 41

<23 41 13> 

max heap : 23 13 (13이 41보다 작으므로 13을 max heap에 대입)

min heap : 41 (max heap의 top인 23을 출력)

<23 41 13 22>

max heap : 22 13 (23이 22보다 크므로 max heap의 top을 min heap에 넣고 pop, 22는 max heap에 대입)

min heap : 41 23

<23 41 13 22 65>

max heap : 23 22 13 (65가 23보다 크므로 min heap의 top을 max heap에 넣고 pop, 65는 min heap에 대입)

min heap : 65 41

뭐 이런식으로 합니다.

https://github.com/blisstoner/BOJ/blob/master/2696.cpp