힙을 이용한 데이터 리스트 병합

 

유전자 관련 생명의학 응용 프로그램에서

대용량 데이터셋을 처리하는 경우를 가정해보겠다.

유사성을 계산하려면 정렬된 DNA 순위가 필요하다.

 

그러나 데이터셋이 너무 방대하기 때문에 단일 머신에서 처리할 수 없다.

그러므로 분산 클러스터에서 데이터를 처리하고 저장하며,

각각의 노드는 일련의 정렬된 값이 있다.

 

주 처리 엔진은 이들 데이터를 모아서 정렬된 단일 스트림으로 변환해야 한다.

다수의 정렬된 배열을 합쳐 하나의 정렬된 배열을 만드는 기능을 벡터로 제작해보자.

 

1. 각각의 리스트는 이미 정렬되어 있기 때문에
   각 리스트의 최소 원소는 맨 앞에 위치한다.
   
   
2. 힙에서 최소 원소를 가져온 후 이를 제거하고,
   최소 원소가 있던 리스트에서 그 다음으로 작은 원소를 선택해 힙에 추가한다.
   
   
3.  힙의 노드는 이 원소를 어느 리스트에서 가져왔는지,
   또한 해당 리스트에서 몇 번째 원소인지를 저장해야한다.

#include <iostream>
#include <algorithm>
#include <vector>

struct node {
	int data;
	int listPosition;
	int dataPosition;
};

std::vector<int> merge(const std::vector<std::vector<int>>& input) {
	auto comparator = [](const node& left, const node& right) {
		if (left.data == right.data)
			return left.listPosition > right.dataPosition;
		return left.data > right.data;
		};

	std::vector<node> heap;
	for (int i = 0; i < input.size(); i++) {
		heap.push_back({ input[i][0], i, 0 });
		std::push_heap(heap.begin(), heap.end(), comparator);
	}

	std::vector<int> result;
	while (!heap.empty())
	{
		std::pop_heap(heap.begin(), heap.end(), comparator);
		auto min = heap.back();
		heap.pop_back();
		result.push_back(min.data);
		int nextIndex = min.dataPosition + 1;
		if (nextIndex < input[min.listPosition].size()) {
			heap.push_back({ input[min.listPosition][nextIndex], min.listPosition, nextIndex });
			std::push_heap(heap.begin(), heap.end(), comparator);
		}
	}
	return result;
}