build strategy

heap 구성 비용

값이 하나씩 들어오는지, 배열이 한 번에 주어지는지, 상위 K개만 필요한지에 따라 힙 구축 전략을 다르게 고른다.

stream 값이 계속 들어옴

매 입력마다 push하고, 필요할 때 pop한다. 온라인 처리에 자연스럽다.

batch 배열이 이미 있음

한 번에 heapify하면 반복 push보다 구축 비용을 낮출 수 있다.

top-k 상위 K개만 필요

크기 K 힙을 유지해 전체 정렬 비용을 피한다.

비용 모델
push 반복값마다 위로 복구O(N log N)
heapify아래 노드부터 내려 복구O(N)
top-kK개만 유지하며 교체O(N log K)
heap 구성 비용 실수 방지 힙 배열은 정렬 배열이 아니므로 중간 원소의 순서를 검사 기준으로 삼지 않는다. 동점 우선순위가 있으면 값만 넣지 말고 비교 키를 함께 설계한다.
연산 규칙 한 번에 받은 데이터는 heapify, 계속 들어오는 데이터는 push, 일부 결과만 필요하면 크기 제한 힙을 우선 검토한다.