고정 K
최소 힙 크기를 K로 묶기새 값이 루트보다 크면 교체하고, 작으면 버려 정렬 비용을 줄입니다.
복합 키
점수와 사용자 기준을 함께 비교점수 동점, 최신성, 사용자 ID처럼 문제 조건에 맞는 비교 함수를 먼저 고정합니다.
윈도우
만료된 데이터 정리시간 구간이 움직이면 lazy deletion이나 카운터로 오래된 항목을 제거합니다.
Top-K 선택 기준
- 전체 정렬이 필요한지, 상위 K만 필요한지 먼저 분리합니다.
- 힙 루트가 현재 후보 중 가장 약한 값인지 확인합니다.
- 윈도우 문제라면 삭제 시점과 중복 값을 별도 상태로 관리합니다.
비용 비교
정렬
O(n log n)
결과 전체가 필요할 때
최소 힙
O(n log K)
상위 K만 유지할 때
윈도우 힙
삽입·만료 관리
스트림 구간이 계속 바뀔 때