Top-K decision table

경계값을 유지할지, 정렬할지, 선택할지 먼저 정한다

Top-K는 상위 K개를 “찾는” 문제가 아니라, 결과에 영향을 주지 않는 값을 언제 버릴 수 있는지 정의하는 문제입니다. 스트림, 정적 배열, 윈도우, 동점 정책이 달라지면 같은 힙 코드도 다른 요구사항이 됩니다.

drop push K answer
경계값 heap[0] 이하는 결과를 바꾸지 못한다.
교체 더 큰 값만 push-pop으로 후보 집합에 넣는다.
출력 힙 내부 순서와 답안 정렬은 별도 단계다.
scope

전역 누적 또는 윈도우

전체 스트림이면 하나의 힙을 유지하고, 구간별 결과면 윈도우마다 상태를 분리합니다.

source

정적 배열 또는 온라인 입력

정적 입력은 정렬·quickselect가 가능하지만, 무한 스트림은 유지 상태가 필요합니다.

accuracy

정확 결과 또는 허용 오차

근사 전략은 오차 범위와 누락 허용 정책이 명시될 때만 선택합니다.

order

선택 집합과 출력 순서

힙 내부 순서는 답안 순서가 아니므로 출력 정렬 요구를 따로 확인합니다.

tie

동점과 복합 키

점수, 시간, ID, 입력 순서 중 무엇이 우선인지 비교 키에 고정합니다.

sort

전체 정렬 후 절단

O(N log N). 입력이 작거나 구현 단순성이 더 중요할 때 적합합니다.

min heap

크기 K 힙 유지

O(N log K), 공간 O(K). 스트림과 큰 입력의 기본 선택입니다.

quickselect

정적 배열의 K번째 경계 선택

평균 O(N). 전체 입력이 메모리에 있고 온라인 갱신이 없을 때 검토합니다.

approximate

근사 후보 유지

대용량 이벤트에서 정확도보다 지연과 메모리 상한이 우선일 때만 사용합니다.

전역 Top-K 한 힙을 계속 갱신 요청 시점 또는 스트림 종료 시점 출력 k=0, k>N, 중복 점수 확인
윈도우 Top-K 윈도우마다 상태를 분리 시간·개수·이벤트 경계마다 출력 늦게 도착한 이벤트와 경계 포함 여부 확인
정적 배열 Top-K 배열 전체를 보고 선택 또는 정렬 계산 완료 직후 출력 출력 정렬과 원본 보존 여부 확인
k = 0

빈 결과

힙 접근 전에 즉시 반환해야 합니다.

k > N

전체 후보 출력

가능한 원소만 정렬해 반환합니다.

equal score

동점 정책

시간, ID, 입력 순서를 비교 키에 넣습니다.

output

힙 순서 착각

힙 pop 결과를 답안 순서로 오해하지 않습니다.