수열을 반으로 나눠서 작은 쪽을 maxHeap에, 큰 쪽을 minHeap에 넣으면 중간값을 항상 조회할 수 있다. 수열의 길이가 홀수면 maxHeap에 하나 더 넣는 것으로 정하고, 수를 읽을 때 어차피 짝수길이에서는 작은 수를 읽도록 하였으므로 항상 maxHeap쪽 root를 읽어서 더해주면 된다.
maxHeap의 root는 minHeap의 root보다 항상 작거나 같아야한다. (불변식) 만약 이 불변식이 깨진다면 그 때 양쪽 root를 서로 바꿔주면 된다.
[New Things]
Collections.reverseOrder()를 사용하면 순서가 자연정렬과 반대인 정렬을 구현할 수 있다.
PriorityQueue는 기본적으로 minHeap이다. (1~10을 넣으면 1부터 나온다.)
https://algospot.com/judge/problem/read/RUNNINGMEDIAN