최종 정리
Top-K는 후보 유지와 출력 정렬을 분리한다
스트림 중에는 K개 후보만 유지하고, 순위표가 필요해지는 마지막 순간에만 K개를 정렬한다. 그래서 메모리와 지연을 동시에 줄인다.
1. 입력 스트림
값이 계속 들어오며 전체 N은 커질 수 있다.
N개 입력
2. K칸 힙 유지
루트보다 큰 값만 교체해 후보 K개를 보존한다.
O(N log K), O(K)
3. 필요할 때 정렬
히프에서 꺼낸 K개만 최종 출력 순서로 정렬한다.
1위
2위
3위
K 확인k=0, k>N, k=1을 먼저 테스트한다.
동점 규칙score가 같을 때 보조 키를 고정한다.
윈도우누적인지 구간별인지 상태 범위를 분리한다.