K=3 min-heap
Top-K는 “루트보다 큰가?”만 보면 된다
전체를 다시 정렬하지 않고 크기 K의 최소 힙을 유지한다. 힙 루트가 현재 Top-K의 경계값이므로, 새 값은 그 경계만 넘으면 교체된다.
9
7
5
8
3
10
4
x > root
경계값을 밀어내고 pop+push로 Top-K 후보를 갱신한다.
x ≤ root
현재 K개보다 작으므로 버려도 최종 결과가 바뀌지 않는다.
상태
힙에는 항상 최대 K개만 남긴다.
시간
새 값 하나당 최대 O(log K)만 쓴다.
핵심
무엇을 저장할지보다 무엇을 버릴지 먼저 정한다.