운영 선택 기준
이 네 가지가 맞으면 힙 Top-K가 정답이다
스트림 입력, 정확한 상위 K, 작은 메모리, 실시간 갱신이 동시에 필요하면 전체 정렬보다 크기 K 최소 힙이 가장 단순하다.
✓
계속 들어오는 입력입력 전체를 보관하기 어렵다.
✓
상위 K만 필요전체 순위표는 요구사항이 아니다.
✓
메모리 상한 O(K)N이 커져도 상태 크기는 K로 고정한다.
✓
즉시 갱신새 값 하나를 O(log K) 안에 반영한다.
선택: 크기 K 최소 힙
루트는 현재 Top-K의 최솟값이다. 루트를 넘는 값만 교체해 후보 K개를 유지한다.
91
82
root
root
88
방법
상태
용도
힙 유지
O(K)
스트림 정확 Top-K
Quickselect
O(N)
정적 배열 1회 계산
전체 정렬
O(N)
전체 순서 필요
힙 유지
상태 O(K), 스트림 정확 Top-K에 적합
Quickselect
상태 O(N), 정적 배열을 한 번 계산할 때 사용
전체 정렬
상태 O(N), 전체 순서가 필요할 때 선택