전략 분기표
Top-K는 입력 범위와 비교 키로 먼저 갈라진다
같은 Top-K라도 전역 누적인지, 구간별 결과인지, 여러 지표를 합산하는지에 따라 상태 초기화와 비교 키가 달라진다.
질문
“하나의 누적 순위인가, 시간 구간별 순위인가, 점수를 계산해야 하는가?”
이 답이 자료구조보다 먼저 정해져야 한다.
global
전역 Top-K
전체 기간의 상위 K를 유지한다. 크기 K 최소 힙 하나로 누적 갱신한다.
window
윈도우 Top-K
구간이 끝나면 출력하고 힙을 초기화한다. 슬라이딩이면 만료 처리가 필요하다.
multi key
다중 키 순위
revenue, click, id를 단일 score나 명시적 tuple로 바꾼 뒤 비교한다.
메모리K가 작을수록 힙 유지가 유리하다.
정렬힙 내부 순서와 출력 순서는 따로 본다.
동점입력 순서나 id 기준을 먼저 고정한다.