Programming Problems/힙

계속적으로 들어오는 스트림에서 중간값 트래킹하기

fw93 2018. 4. 22. 12:26

min heap와 max heap을 유지해 가며 서로의 균형을 유지하면 top() 의 값들이 median이다.


계속적으로 들어오기 때문에 힙이 유리하지, 단 한번 찾는거면 partitioning 이 O(N) 으로 가장 빠르다.

이 알고리즘은 O(NligK) 이다.