우선 대기 열 병합 가능: 왼쪽 트 리 와 경사 로

우선 대기 열 을 합 쳐 야 할 때 가 있 습 니 다. 이 진 더미 에 대해 서 는 O (N) 의 복잡 도 로 만 쌓 을 수 있 습 니 다. 키 값 과 쌓 는 순서 외 에는 아무것도 없 기 때 문 입 니 다.
통합 의 복잡 도 를 O (LogN) 로 낮 추 려 면 경사 로 (왼쪽 트 리), 2 항 로 등 데이터 구 조 를 사용 할 수 있다.피 폴 라 치 더 우, 많은 조작 이 O (1) 의 이론 적 복잡 도 이지 만 사고 복잡 도와 프로 그래 밍 복잡 도...
두 가지 더 미 는 조금 알 았 지만 성질 같은 것 을 조금 알 지 못 했 을 뿐 구체 적 인 조작 은 아직 할 줄 몰 랐 다.시간 나 면 한번 해 보고 싶 어 요.피 폴 라 치 더 는 됐 고..
왼쪽 트 리 의 성질 은 왼쪽 트 리 의 0 경로 가 오른쪽 트 리 보다 길지 않 아서 나무 가 심각하게 왼쪽으로 쏠 린 다 는 것 이다.두 그루 의 나 무 를 합 쳐 꼭대기 요소 의 크기 를 비교 하고 한 그루 의 나무의 오른쪽 나무 와 다른 나 무 를 다시 합 치면 된다.합 친 트 리 오른쪽 트 리 의 0 경로 가 왼쪽 트 리 보다 작 으 면 좌우 트 리 를 교환 합 니 다.삽입 하면 하나의 요소 만 있 는 왼쪽 트 리 와 다른 트 리 를 합 친 것 으로 볼 수 있다.삭제 하면 좌우 트 리 를 합치 면 됩 니 다.나 무 는 퇴적 성질 에 부합 하기 때문에 최소 값 을 취 하 는 작업 도 마찬가지다.
경사 더 미 는 왼쪽 편 나무의 자체 조정 형식 으로 말하자면 간략화 판 이다.우 리 는 유지 경로 가 길 필요 가 없습니다. 합병 할 때마다 좌우 서브 트 리 를 교환 합 니 다. 이렇게 균등 하 게 할당 하 는 작업 시간 은 변 하지 않 습 니 다. 사상 은 Splay 와 AVL 과 유사 합 니 다.구체 적 인 실현 은 코드 를 몇 줄 만 적 게 치면 된다.
왼쪽 편 나무의 입문 문 제 는 HDU 1512 이 며, 동시에 집 을 찾 아 아버 지 를 찾는다.
저 는 여기 보고 썼어 요. http://www.cnblogs.com/lxf90/archive/2011/04/07/2008180.html
다음은 이 문제 와 왼쪽 트 리 에 대한 PPT 링크 http://oi.imzzl.com/2010/07/610.html 입 니 다.
코드: (경사 더미 입 니 다. 제거 / / 왼쪽 트 리 입 니 다)
 

#include <stdio.h>



#define MAXN 100000



struct node

{

    int dis,l,r,strong;

}tree[MAXN];



int i,j,k,m,n;

int father[MAXN];

int x,y,fx,fy;







void swap(int *x, int *y)

{

    int temp;

    temp = *x;

    *x = *y;

    *y = temp;

}



int find(int x)

{

    if (x != father[x])

        father[x] = find(father[x]);

    return father[x];

}





int merge(int x, int y)

{

    if (x == 0)

        return y;

    if (y == 0)

        return x;

    if (tree[x].strong < tree[y].strong)

        swap(&x, &y);

    tree[x].r = merge(tree[x].r, y);

    int l = tree[x].l;

    int r = tree[x].r;

    father[r] = x;

   // if (tree[l].dis < tree[r].dis)

        swap(&tree[x].l, &tree[x].r);

   // if (tree[x].r == 0)

   //     tree[x].dis = 0;

   // else

   //     tree[x].dis = tree[r].dis + 1;

    return x;

}





int del(int x)

{

    int l,r;

    l = tree[x].l;

    r = tree[x].r;

    father[l] = l;

    father[r] = r;

    tree[x].l = tree[x].r = tree[x].dis = 0;

    return merge(l, r);

}





void fight(int x , int y)

{

    int left,right,now;

    tree[x].strong /= 2;

    tree[y].strong /= 2;

    left = del(x);

    right = del(y);

    left = merge(left, x);

    right = merge(right ,y);

    now = merge(left, right);

    printf("%d
", tree[now].strong);

}





int main()

{

    while (scanf("%d", &n) == 1)

    {

        for (i = 1; i <= n; i++)

        {

            scanf("%d", &tree[i].strong);

            tree[i].l = tree[i].r = tree[i].dis = 0;

            father[i] = i;

        }

        scanf("%d", &m);

        for (i = 1; i <= m; i++)

        {

            scanf("%d%d", &x, &y);

            fx = find(x);

            fy = find(y);

            if (fx == fy)

                printf("-1
");

            else fight(fx, fy);

        }

    }

    return 0;

}

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
 
참고 자료:
CLRS
데이터 구조 와 알고리즘 분석