외부 정렬 : 멀티 웨이 병합에서 멀티 웨이 병합

Question

이 작업은 K 요소에서

솔루션 가장 작은 요소를 찾을 수 있습니다 : 우선 순위 큐

을

아이디어 :로 저장, 최초의 K 실행에서 가장 작은 요소를 가지고 힙 트리의 주 메모리.

그런 다음 힙에서 가장 작은 요소를 반복적으로 출력합니다. 가장 작은 요소는 그 요소가 나온 실행의 다음 요소로 바뀝니다.

첫 번째 실행 집합이 끝나면 다음 실행 집합과 동일하게 실행하십시오.

는 K 미만, 우리가 작품을 병합하는 방법을 여러 방법으로 병합 알고리즘 즉,의 요소를 정렬 할 수 있습니다 방법 메모리 크기 M 예 경우를 들어

K

보다 작은 경우 크기의 내 메인 메모리 (M)를 가정 내 M = 3 그리고 난 다음 한

TAPE1 : 8 9 10 TAPE2 : 11 12 13 Tape3 : 14 15 16 Tape4 : 4 5 6

우리가 읽을 수 있기 때문에 작동 병합 muliway 방법

내 질문 8, 11, 14 및 빌드 우선 순위 대기열에 8을 놓고 테이프를 출력 한 다음 Tape1을 전달합니다 , 나는 Tape4가 읽히고 어떻게 출력 테이프에 이미 기록 된 것과 비교할 것인가?

감사합니다.

Answer 1

작동하지 않습니다. 사용 가능한 메모리가 충분히 작은 k을 선택해야합니다.

이 경우 처음 3 개의 테이프를 3 방향 병합 한 다음 그 결과와 나머지 1 개의 테이프를 양방향으로 병합 할 수 있습니다. 또는 3 쌍의 2-way 병합 (두 쌍의 테이프를 결합한 다음 결과 결합)을 수행 할 수 있습니다. 이는 구현이 더 간단하지만 더 많은 테이프 액세스를 수행합니다.

이론적으로 우선 순위 대기열을 포기할 수 있습니다. 그렇다면 k 요소를 메모리에 저장할 필요는 없지만 가장 작은 것을 찾으려면 모든 k 테이프의 다음 요소를 자주 확인해야합니다.