DAA-최적의 병합 패턴

길이가 다른 정렬 된 파일 세트를 하나의 정렬 된 파일로 병합합니다. 결과 파일이 최소 시간에 생성되는 최적의 솔루션을 찾아야합니다.

정렬 된 파일의 수를 지정하면 여러 가지 방법으로 하나의 정렬 된 파일로 병합 할 수 있습니다. 이 병합은 쌍으로 수행 할 수 있습니다. 따라서 이러한 유형의 병합을 다음과 같이 호출합니다.2-way merge patterns.

페어링마다 다른 시간이 필요하므로이 전략에서는 여러 파일을 함께 병합하는 최적의 방법을 결정하려고합니다. 각 단계에서 가장 짧은 시퀀스 두 개가 병합됩니다.

병합하려면 p-record file 그리고 q-record file 아마도 필요하다 p + q 레코드 이동, 분명한 선택은 각 단계에서 가장 작은 두 파일을 병합하는 것입니다.

양방향 병합 패턴은 이진 병합 트리로 나타낼 수 있습니다. 일련의n 정렬 된 파일 {f₁, f₂, f₃, …, f_n}. 처음에 이것의 각 요소는 단일 노드 이진 트리로 간주됩니다. 이 최적의 솔루션을 찾기 위해 다음 알고리즘이 사용됩니다.

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

이 알고리즘의 끝에서 루트 노드의 가중치는 최적의 비용을 나타냅니다.