Top-K 경계 힙

K의 크기 검토

K가 N에 가깝다면 정렬과 힙의 비용 차이가 줄고, K가 작을수록 힙 유지가 유리합니다.

큰 K개를 원하면 현재 후보 중 가장 작은 값을 루트에 두어 새 값과 비교합니다.

경계

새 원소가 경계를 넘으면 pop 후 push하고, 아니면 버려 후보 크기를 K로 유지합니다.

stream

같은 값이나 같은 점수의 순서가 필요하면 값 외에 원래 순서나 id를 함께 저장합니다.

tie

Sort

전체 순서가 필요할 때 단순하고 안정적 O(N log N)이지만 구현과 검증이 쉽습니다.

all

Heap K

K개 후보만 유지해 O(N log K) 스트림이나 메모리 제한 상황에서 강합니다.

partial

Quickselect

순서 없는 K개 경계만 빠르게 찾음 평균 O(N)이지만 최악과 구현 안정성을 고려해야 합니다.

select

K=0/N K가 0이거나 N보다 큰 경우 반환 정책을 먼저 정합니다.

출력 정렬 힙에서 꺼낸 결과가 원하는 순서인지, 추가 정렬이 필요한지 확인합니다.

메모리 스트림에서는 입력 전체를 저장하지 않아도 되는지가 장점입니다.