중앙값 찾기 / [인덱스트리, pq ]

[WonYong-Jang]

인덱스 트리 이용

• 백준 9426
• 각 노드를 숫자로 받고 트리를 구성
• 입력을 받자마자 tree[idx]++ update 해주고 해당 구간까지 도달하면 query를 날려서 k 번째를 찾아감
• left, right 자식노드를 확인하는데 if(k <= left) 라면 오른쪽은 볼필요 없으므로 왼쪽 자식노드 이동
• 그러지 않고 k 가 더 크다면 k = k - left 로 갱신하여 오른 쪽 확인
• 리프 노드 도달할때까지 반복

[WonYong-Jang]

max heap / min heap 이용

설명 참고 : https://www.crocus.co.kr/625

1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다
[ 최대 힙의 크기 == 최소힙의 크기  || 최대 힙 + 1 == 최소힙의 크기 ]
2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다. [최대 힙의 원소 <= 최소 힙 원소 ] 
이때 알고리즘에 맞지 않는 다면 최대 힙, 최소 힙의 가장 위의 값을 swap
=> 이때 이 두가지 규칙을 유지해 준다면 항상 최대 힙 top 갑이 중간값이 된다.