K 길 병합 (외부 정렬) 과 패자 트 리

4467 단어 알고리즘
일 K 로 병합 정렬 및 최적화 - 패자 트 리  외부 정렬 은 두 개의 상대 적 으로 독립 된 단계 로 구성 된다.우선, 사용 가능 한 메모리 크기 에 따라 외부 에 저 장 된 n 개의 기록 을 몇 개의 길이 의 하위 파일 이나 세그먼트 로 나 누고 모든 하위 파일 을 읽 어서 단독 내 정렬 한 다음 에 외부 저장 소 를 다시 씁 니 다.그 다음 에 이런 병합 구간 을 충분히 병합 하여 병합 구간 이 점점 커지 고 모든 병합 구간 이 질서 가 있 을 때 까지 한다.  일반 2 번 병합 으로 인해 디스크 의 읽 기와 쓰기 횟수 가 매우 많 고 k 번 을 합 리 적 으로 사용 하면 디스크 의 읽 기와 쓰기 횟수 를 합 리 적 으로 줄 일 수 있다.그러나 전통 적 인 k 길 병합 은 또 다른 문 제 를 가 져 왔 다. 매번 에 k 개의 질서 있 는 구간 의 기록 을 병합 할 때마다 k - 1 차 비 교 를 해 야 한다.그러나 패자 트 리 를 사용 하면 비교 횟수 를 logk 로 낮 추어 최종 병합 시간 이 k 값 의 영향 을 받 지 않도록 할 수 있 습 니 다.  패자 트 리 도 완전 이 진 트 리 입 니 다. 나무 모양 선택 정렬 의 변형 입 니 다. 패자 트 리 의 부모 노드 는 두 노드 간 의 패 자 를 기록 하고 승 자 를 더 높 은 층 의 경기 에 참가 하 게 합 니 다.참조 코드
#include 
using namespace std;

#define LEN 10          //      
#define MINKEY -1     //      
#define MAXKEY 100    //   ,            

struct Array
{
    int arr[LEN];
    int num;
    int pos;
}*A;

    int k,count;
    int *LoserTree,*External;

void Adjust(int s)
{
    int t=(s+k)/2;
    int temp;
    while(t>0)
    {
        if(External[s] > External[LoserTree[t]])
        {
            temp = s;//temp   
            s = LoserTree[t]; //  s   ，        
            LoserTree[t]=temp;
        }
        t=t/2;
    }
    LoserTree[0]=s;
}

void CreateLoserTree()
{
    External[k]=MINKEY;
    int i;
    for(i=0;ifor(i=k-1;i>=0;i--)Adjust(i);
    //for(i=0;i
}

void K_Merge()
{
    int i,p;
    for(i=0;i//cout<
        A[i].pos++;
    }
    CreateLoserTree();
    int NO = 0;
    while(NO0];
        cout<",";
        NO++;
        if(A[p].pos>=A[p].num)External[p]=MAXKEY;
        else 
        {
            External[p]=A[p].arr[A[p].pos];
            A[p].pos++;
        }
        Adjust(p);
    }
    cout<int main()
{
    freopen("in.txt","r",stdin);

    int i,j;
    count=0;
    cin>>k;
    A=(Array *)malloc(sizeof(Array)*k);
    for(i=0;icin>>A[i].num;
        count=count+A[i].num;
        for(j=0;jcin>>A[i].arr[j];
}
A[i].pos=0;
}
LoserTree=(int *)malloc(sizeof(int)*k);
External=(int *)malloc(sizeof(int)*(k+1));
K_Merge();
return 0;
}

코드 는 블 로 거 하 러 소 에서 유래 했다.
동적 계획 의 최대 K 곱 하기 문제
🔥 TIL - Day 83 Spring AOP를 이용한 예외발생 시 재시도 구현

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage