2.5.3 실습 문제 5: 힙을 이용한 데이터 리스트 병합

유전자 관련 생명의학 응용 프로그램에서 대용량 데이터셋을 처리하는 경우를 가정해보겠습니다. 유사성을 계산하려면 정렬된 DNA 순위가 필요합니다. 그러나 데이터셋이 너무 방대하기 때문에 단일 머신에서 처리할 수 없습니다. 그러므로 분산 클러스터에서 데이터를 처리하고 저장하며, 각각의 노드는 일련의 정렬된 값이 있습니다. 주 처리 엔진은 이들 데이터를 모아서 정렬된 단일 스트림으로 변환해야 합니다. 그러므로 다수의 정렬된 배열을 합쳐서 하나의 정렬된 배열을 만드는 기능이 필요합니다. 이제 벡터를 이용하여 이러한 상황을 시뮬레이션하는 프로그램을 작성하기 바랍니다.

실습 문제를 해결하기 위해 다음 단계를 따라하세요.

  1. 각각의 리스트는 이미 정렬되어 있기 때문에 각 리스트의 최소 원소는 맨 앞에 위치합니다. 이들 원소로부터 최솟값을 빠르게 선택하기 위해 힙을 사용할 것입니다.

  2. 힙에서 최소 원소를 가져온 후 이를 제거하고, 최소 원소가 있던 리스트에서 그다음으로 작은 원소를 선택해 힙에 추가합니다.

  3. 힙의 노드는 이 원소를 어느 리스트에서 가져왔는지, 또한 해당 리스트에서 몇 번째 원소인지를 저장해야 합니다.

이 알고리즘의 시간 복잡도를 계산해보겠습니다. 리스트가 K개 있다면 힙의 크기는 K가 되고, 모든 힙 연산의 시간 복잡도는 O(log K)가 됩니다. 힙을 구성하는 데는 O(K log K)가 소요됩니다. 그런 다음 각 원소에 대해 힙 연산을 수행해야 합니다. 전체 원소 개수는 N×K입니다. 그러므로 전체 시간 복잡도는 O(NK log K)입니다.

이 알고리즘에서 흥미로운 사실은 한꺼번에 N×K개의 원소를 다 저장하여 사용하지 않아도 된다는 점입니다. 앞에 설명한 시나리오를 살펴보면 특정 시점에서는 K개의 원소만 저장하고 있어도 됩니다. 여기서 K는 리스트 개수이며, 분산 시스템의 노드 개수와 같습니다. 실제 K 값은 그리 크지 않습니다. 힙을 사용함으로써 한 번에 하나의 결과 값을 얻을 수 있고, 이를 곧바로 처리하거나 또는 다른 곳으로 다시 스트리밍할 수 있습니다.