우선 순위 큐

[1. 문제 설명]

수열에 새로운 수가 추가 될 때 마다

수열 내 중간 값들의 합을 출력한다.

[2. 풀이 접근]

수열의 중간 값은 정렬 된 수열 내 중앙에 오는 값이며,

수열의 길이가 짝수 개인 경우 둘 중 더 작은 값이다.

원소 추가 때마다 정렬을 하면 N²LogN 이므로 시간초과가 발생한다.

maxHeap 에는 정렬된 수열의 왼쪽 값들이 저장되고

minHeap 에는 정렬된 수열의 오른쪽 값들이 저장된다 하면

중간 값은 maxHeap 의 root 와 minHeap 의 root 사이에 존재하게 된다.

수열의 길이가 홀수 개인 경우와

(empty 인 경우 최대 힙의 root 가 중간 값이 된다.)

짝수 개인 경우 더 작은 값이 중간 값이 되는 특성을 이용하여

중간 값 까지 최대 힙에 저장하도록 한다.

여기서 항상 최대 힙의 개수가 최소 힙의 개수 이상이 되야 한다는 조건이 성립한다.

(수열의 길이가 짝수 개인 경우는 같고, 홀수 개인 경우는 하나 더 많다.)

두번째 조건은 최대 힙의 root 가 항상 최소 힙의 root 보다 작아야 한다.

(수열의 길이가 같은 경우 더 작은 값이 중간 값이 되야 한다.)

위 두가지 조건을 지켜서 적절한 힙에 푸쉬하고

root 에 저장 된 값은 swap 하도록 구현하도록 한다.

[3. 코드]

test_kernelv2