Top-K 빈도

전체 정렬 대신 힙에는 상위 K 후보만 남긴다

`values=[1,1,1,2,2,3,3,3,3,4]`, `k=2`에서는 빈도 맵을 만든 뒤 최소 힙 크기를 2로 제한합니다. 새 후보를 넣었을 때 크기가 넘으면 가장 작은 빈도를 버려 Top-K 후보만 유지합니다.

빈도를 막대로 보고, 힙에는 K개만 남긴다

k = 2 min-heap

frequency map

1
3
2
2
3
4
4
1

초록 막대는 최종 Top-K 후보, 주황 막대는 힙 크기 초과 때 밀려나는 후보입니다.

heap snapshots

after push 2 size = 2
(2,2) (3,1)

루트는 현재 후보 중 가장 약한 빈도입니다.

push 3 then pop size = 3 -> 2
(2,2) (3,1) (4,3)

K를 넘는 순간 루트 `(2,2)`가 제거됩니다.

final heap Top-K kept
(3,1) (4,3)

출력 직전에만 빈도 내림차순으로 정렬합니다.

1

빈도 맵 생성

입력을 한 번 순회해 `key -> count`를 만듭니다. 이때 비용은 `O(N)`, 공간은 고유 키 수 `U`만큼 필요합니다.

1:3 2:2 3:4 4:1
2

최소 힙에 push

`(count, key)`를 기준으로 넣으면 힙의 루트가 현재 후보 중 가장 약한 항목이 됩니다. 동점 정책은 이 시점에 고정합니다.

(3,1) (2,2) (4,3)
3

크기가 K를 넘으면 pop

힙 크기가 `k`를 넘는 순간 가장 작은 빈도를 제거합니다. 그래서 전체 후보를 모두 정렬하지 않아도 상위 후보만 남습니다.

pop (2,2) keep size 2
4

결과를 기준대로 정렬

힙에서 꺼낸 후보는 표시용으로 다시 빈도 내림차순 정렬합니다. 최종 결과는 문제의 출력 정책과 동점 규칙을 따라야 합니다.

(3,4) (1,3)

k=2 힙 상태 추적

push 1 [(3,1)]
push 2 [(2,2), (3,1)]
push 3 [(2,2), (3,1), (4,3)]
pop (2,2)를 제거하고 [(3,1), (4,3)] 유지

핵심은 “모든 항목을 정렬하지 않는다”입니다. 힙에는 최대 K개만 남기고, 출력 직전에만 표시 기준대로 정렬합니다.