Top-K 설계는 정확도, 시간 범위, 상태 크기로 고른다
힙을 쓰기 전에 정확한 K가 필요한지, 윈도우가 있는지, K개만 저장해도 되는지를 먼저 고정한다.
| 축 | 선택지 | 자료구조 | 확인할 조건 |
|---|---|---|---|
| 정확도 | 정확 Top-K / 근사 | heap / sketch | 오차 허용 여부 |
| 시간 범위 | 전체 / 윈도우 | heap / heap+expire | 만료 정책 존재 여부 |
| 상태 크기 | O(K) / O(N) | min-heap K칸 | K가 N보다 충분히 작은지 |
| 동점 | score, id, 입력 순서 | 비교 키 튜플 | 동점 출력 순서 고정 |
결정: 윈도우가 닫힐 때 만료하고, 유지 중에는 K칸 최소 힙으로 경계값만 비교한다.