신기한 나무

트리: 두 결점 사이에 경로가 하나만 있는 무방향 그림입니다.두 갈래 나무: 매 결점마다 최대 두 개의 결점이 있다.만 두 갈래 나무: 두 갈래 나무 중의 모든 내부 두 갈래 나무는 두 개의 결점이 있는데 이런 두 갈래 나무를 만 두 갈래 나무라고 부른다.(깊이가 h이고 2^h-1개의 결점이 있는 두 갈래 나무.)완전 두 갈래 나무: 두 갈래 나무는 맨 오른쪽 위치에 하나 또는 몇 개의 잎 결점이 부족한 것을 제외하고 다른 것은 풍만하다. 그러면 이런 두 갈래 나무는 완전 두 갈래 나무다.(만 두 갈래 나무는 완벽한 완전 두 갈래 나무다.)

    1
  2   3
4  5 6  7

완전 두 갈래 나무를 위에서 아래로, 왼쪽에서 오른쪽으로 번호를 매긴다. 만약에 한 부결점의 번호가 k라면, 그의 왼쪽 자결점은 2*k( 0 , 2*k+1), 오른쪽 결점은 2*k+1( 0 , 2*k+2)이다.만약 자식 결점 번호가 x인 것을 알고 있다면, 부결점 번호는 x/2, 완전한 두 갈래 나무에 N개의 결점이 있다면, 그 높이는 log2^N, 약어는 logN이다.

1. 더미

최대 더미: 모든 아버지 결점은 자식 결점보다 크다.최소 더미: 모든 아버지 결점은 자식 결점보다 작다.

 :
void siftdown(int i){
    int t, flag = 0;
    // ， ， 
    while( i * 2 <= n && flag == 0){
        // ， t 
        if(h[i] > h[i * 2]){
            t = i * 2;
        }else{
            t = i;
        }
        if( i * 2 + 1 <= n){
            if(h[t] > h[i *2 + 1]){
                t = i * 2 + 1;
            }
        }
        if( t != i){
            swap(t,i);
            i = t;
        }else{
            flag = 1;
        }
    }
    return ;
}

 :
void siftup(int i){
    int flag = 0;
    if(i == 1) return; // ， 
    while(i != 1 && flag == 0){
        if(h[i/2] > h[i]){
            //  
             swap(i,i/2);
        }else{
            flag = 1;
        }
        i = i / 2;
    }
    return ;
}

 ： ， 。 i O(logi), O(NlogN)
n = 0;
for(i = 1; i <= m;i++){ n++; h[n] = a[i]; //h[n]  siftup(n); }

 2：
for(i = n/2; i >= 1; i--){ siftdown(i); }

2. 더미 정렬

정렬 시간의 복잡도는 O(NlogN)입니다.작은 것부터 큰 것까지 정렬: 최소 더미를 만들고 맨 위 요소를 삭제하고 맨 위 요소를 출력하거나 새 그룹에 넣습니다. 더미가 비어 있을 때까지.

// ( )  ( )
int deletemax(){
    int t;
    t = h[1];
    h[1] = h[n]; // 
    n--;
    siftdown(1);
    return t;
}

쌓기와 쌓기 정렬의 전체 코드는 다음과 같다.

#include <stdio.h>
int h[101];
int n; // 

// 
void swap(int x, int y){
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
    return ;
}

// 
void siftdown(int i){
    int t, flag = 0;
    while(2 * i <= n && flag == 0){
        if(h[i] > h[2 * i]){
            t = 2 * i;      
        }else{
            t = i;
        }
        if(2 * i + 1 <= n){
            if(h[t] > h[2*i+1]){
                t = 2*i + 1;
            }
        }
        if(t != i){
            swap(h[t],h[i]);
            i = t;
        }else{
            flag = 1;
        }
    }
    return ;
}

// 
void create(){
    int i;
    for(i = n/2; i >=1; i--){
        siftdown(i);
    }
    return ;
}

// 
int deletemax(){
    int t;
    t = h[1];
    h[1] = h[n];
    n--;
    siftdown(1);
    return t;
}

int main(){
    int i, num;
    scanf("%d", &num);

    for(i = 1; i <= num; i++){
        scanf("%d", &h[i]);
    }
    n = num;

    // 
    create();

    // ， n ， 
    for(i = 1; i <= num; i++){
        printf("%d ",deletemax());
    }
    getchar();
    return 0;
}

3. 최대 더미 정렬

void heapsort(){
    while(n > 1){
        swap(1,n);
        n--;
        siftdown(1);
    }
    return ;
}

4. 수집

본질은 삼림을 보호하는 것이다.처음에 삼림의 모든 점은 고립되었다. 즉, 모든 점은 하나의 결점만 있는 나무이고, 그 후에 몇 가지 조건을 통해 점차적으로 이 나무들을 하나의 큰 나무로 합쳤다.

#include<stdio.h>
int f[1000] = {0}, n, m, k, sum = 0;
// 
void init(){
    int i;
    for(i = 1; i <= n; i++){
        f[i] = i;
    }
    return ;
}

// 
int getf(int v){
    if(f[v] == v){
        return v;
    }else{
        f[v] = getf(f[v]);
        return f[v];
    }
}

void merge(int v, int u){
    int t1,t2;
    t1 = get(v);
    t2 = get(u);
    if(t1 != t2){
        f[t2] = t1;
    }
    return ;
}

int main(){
    int i,x,y;
    scanf("%d %d", &n, &m);

    // 
    init();
    for(i = 1; i<= m;i++){
        scanf("%d %d",&x, &y);
        merge(x,y);
    }

    // 
    for(i = 1; i<= n; i++){
        if(f[i] == i){
            sum++;
        }
    }
    printf("%d
",sum);
    getchar();
    return 0;
}