K-way 병합 알고리즘에서 힙의 역할은 무엇인가?

K개 정렬 리스트의 맨 앞 요소 중 최솟값을 빠르게 찾는 역할이다. 모든 리스트를 선형 탐색하면 O(K)가 걸리지만 최소 힙을 쓰면 O(log K)로 줄어든다.

각 리스트가 이미 정렬되어 있어 전체 최솟값은 항상 각 리스트의 첫 원소 중 하나다. 최소 힙은 이 K개 후보를 트리 구조로 관리하며 가장 작은 값을 바로 꺼내준다.

최솟값을 뽑은 리스트에서 다음 원소를 하나 읽어 다시 힙에 넣는 과정을 반복한다. N개 원소를 병합하는 전체 시간 복잡도는 O(N log K)가 된다. 디스크 I/O 비용이 큰 외부 정렬에서 CPU 비교 연산 시간을 크게 아낀다.