K-way 병합 시 최소 힙 대신 패자 트리를 사용하는 이유는 무엇인가?

다음 승자를 결정할 때 부모 노드 하나와만 비교하여 연산량을 줄이기 때문이다.

최소 힙에서 최솟값을 꺼내면 끝 노드가 루트로 이동한다. 이후 자식 노드 둘 중 작은 값을 찾고 그 값과 자신을 비교한다. 바닥까지 내려가며 매 단계마다 두 번씩 비교가 일어난다.

패자 트리는 부모 노드에 패자 정보를 저장한다. 새 값이 들어오면 루트까지 올라가며 만나는 부모와 한 번씩만 비교한다. 자식끼리 비교하는 과정이 사라져 비교 횟수가 반으로 줄어든다.

대용량 데이터를 다루는 외부 정렬에서는 K가 수백 이상으로 커진다. 이때 패자 트리를 쓰면 비교 비용이 줄어 병합 속도가 빨라진다.