Merge k Sorted Lists

각 행마다 pos[r] 인덱스 하나를 두어, 아직 사용하지 않은 해당 행 r의 첫 번째 값, 즉 행의 맨 앞 원소를 가리키게 합니다. 사용하지 않은 값 중 가장 작은 값은 반드시 이 맨 앞 원소 중 하나입니다. 행 r에서 사용하지 않은 모든 값은 pos[r] 위치나 그 뒤에 있고, 행은 정렬되어 있으므로 그중 맨 앞 원소보다 작은 값은 없습니다.

따라서 아직 값이 남아 있는 모든 행을 살펴 가장 작은 맨 앞 원소를 찾고, 그 값을 추가한 다음 해당 행의 인덱스를 한 칸 앞으로 옮깁니다. N개의 값을 모두 꺼낼 때까지 반복합니다. 이것은 병합 정렬의 병합 단계이며, 두 목록을 k개로 확장한 것입니다.

첫 번째 예에서 맨 앞 원소는 처음에 2, 1, 3이므로 1이 먼저 나오고 두 번째 행의 맨 앞 원소는 4가 됩니다. 그런 다음 2(맨 앞 원소 2, 4, 3), 3(맨 앞 원소 6, 4, 3), 4, 그리고 세 번째 행을 비우는 5가 나옵니다. 마지막 세 차례에는 6과 10만 비교하고, 다음에는 9와 10을 비교한 뒤, 마지막으로 10만 남습니다.

비용은 N개의 각 값에 대해 k번 비교하는 것입니다. 값이 하나씩 들어 있는 행이 10^4개라면 비교 횟수는 10^8번입니다. C, Java 또는 JavaScript는 1초 이내에 처리하지만, Python은 10초 넘게 걸립니다. 또한 N과 k를 모두 두 배로 늘리면 어떤 언어든 네 배 느려집니다. 추적 결과에서 낭비가 드러납니다. 값을 하나 고른 뒤 바뀐 맨 앞 원소는 하나뿐인데, 다음 차례에 다시 k개를 모두 읽습니다.

스캔은 가장 작은 값을 찾기 위해 k개의 머리 값을 다시 확인합니다. 하지만 지난 라운드 이후 바뀐 머리 값은 하나뿐입니다. 최소 힙은 바로 이런 경우에 사용합니다. 숫자 집합을 저장하고 가장 작은 값을 맨 위에 두며, 맨 위 값을 꺼내거나 숫자를 추가하는 데 각각 O(log size)의 비용이 듭니다.

각 행의 첫 번째 값을 행 번호와 함께 힙에 넣습니다. 그런 다음 다음을 반복합니다. 가장 작은 쌍 (value, row)을 꺼내 value를 추가하고, 해당 행에 다음 값이 있으면 같은 태그를 붙여 힙에 넣습니다. 힙에는 값이 남아 있는 각 행의 머리 값이 정확히 하나씩 들어 있으므로, 맨 위 값은 전체에서 아직 사용하지 않은 값 중 가장 작습니다. 스캔의 규칙을 더 빠르게 적용하는 방법입니다.

행 번호를 0부터 매겨 첫 번째 예제를 따라가 봅시다. 힙은 2 (행 0), 1 (행 1), 3 (행 2)으로 시작합니다. 1을 꺼내고 행 1의 다음 값인 4를 넣습니다. 2를 꺼내고 행 0의 다음 값인 6을 넣습니다. 3을 꺼내고 행 2의 다음 값인 5를 넣습니다. 4를 꺼내고 10을 넣습니다. 5를 꺼냅니다. 행 2의 값이 모두 사용되었으므로 아무것도 넣지 않고 힙에는 6과 10만 남습니다. 6을 꺼내고 9를 넣습니다. 9를 꺼낸 다음 10을 꺼냅니다. 결과는 [1, 2, 3, 4, 5, 6, 9, 10]입니다.

각 값은 힙에 한 번 들어가고 한 번 나옵니다. 힙에는 최대 k개의 항목만 있으므로, 총 2N번의 각 연산에 O(log k)의 비용이 듭니다. N = k = 10^4이면 약 2 × 10^4 × 14, 즉 3 × 10^5회 미만의 연산으로, 스캔의 10^8회와 비교됩니다. 힙은 O(k) 메모리를 사용하며 O(N)은 사용하지 않습니다. 각 행의 머리 값 하나만 보관하고 그 뒤의 값은 보관하지 않기 때문입니다.

여러 구현에서는 각 행의 머리 값에 따라 정렬된 행 번호 배열로 힙을 직접 만듭니다. 슬롯 i의 자식은 2i+1과 2i+2에 있습니다(1부터 세는 Lua와 R에서는 2i와 2i+1에 있습니다). 이렇게 하면 작업도 줄어듭니다. 맨 위 행의 머리 값을 꺼낸 뒤에도 그 행의 다음 값은 더 작지 않으므로, 해당 행은 맨 위에 남아 한 번만 아래로 내려가면 됩니다. 꺼내기 후 넣기를 하는 것보다 효율적입니다.