《啊哈！算法》第7章 神奇的树

第3节 堆排序

把n个元素建立一个堆，首先将这n个结点以自顶向下、从左到右的方式从1到n编码，这样可以把n个结点转换成一颗完全二叉树

紧接着从最后一个非叶子结点（结点编号为n/2）开始到根节点（结点编号为1），逐个扫描所有结点，根据需要将当前结点向下调整，直到以当前结点为根结点的子树符合堆的特性。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


//向下调整函数
void shiftdown(vector<int>& a, int n,int index){
    while(index*2<= n ){
        int t = index;
        if(a[t] > a[2*index]) t = 2*index;
        if( 2*index+1 <= n &&  a[t] > a[2*index+1] ) t = 2*index+1;
        if(t!=index) {swap(a[t],a[index]); index = t;}
        else break;
    }
}

//删除最大的元素
int deletemax(vector<int>& a , int& n){
    int res = a[1];
    swap(a[1],a[n]);
    n--;
    shiftdown(a,n,1);
    return res;
}

//向上调整函数
void shiftup(vector<int>& a, int n, int index){
    if(index == 1) return;
    while(index!=1){
        if(a[index] < a[index/2]) swap(a[index],a[index/2]);
        else break;
        index/=2;
    }

}

// 创建堆
void make_heap(vector<int>& a, int n){
    //注意索引是从0开始的
    for(int i = n/2; i> 0; -- i){
        shiftdown(a,n,i);
    }
    
}

void heap_sort(vector<int>& a){
    int n =a.size()-1;
    while( n > 1){
        swap(a[1],a[n]);
        n--;
        shiftdown(a,n,1);
    }
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n+1,0);
    for(int i = 1 ; i <= n; ++ i){
        cin >> a[i];
    }

    //建堆
    make_heap(a,n);

    heap_sort(a);
    
    for(int i = 1 ; i <= n; ++ i){
        cout<<a[i]<<" ";
    }    
    cout<<endl;
    int num = n;
    for(int i = 1; i <= n; ++ i){
        cout<<deletemax(a,num)<<endl;
    }

}

 第4节 并查集

并查集的优化有两种，一种是路径压缩，一种是按秩合并，具体的可以参考《算法导论》

/*
 *并查集操作
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int f[1000]={0};

void make_set(int size){
    for(int i =1; i <= size; ++ i ) f[i] = i;
}


//采用路径压缩的方法查找元素
int find_set(int x){
    if(f[x] == x) return x;
    else{
         f[x] = find_set(f[x]);  //查找x元素所在的集合，回溯时压缩路径
         return f[x];
    }

}

void union_set(int x, int y){
    int t1 = find_set(x), t2 = find_set(y);
    if(t1 != t2){
        f[t2] = t1;
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    make_set(n);
    for(int i = 1; i<=m; ++ i){
        int x,y;
        cin >> x >> y;
        union_set(x,y);
    }
    int sum = 0;
    for(int i = 1; i<= n; ++ i){
        if(f[i] == i) sum++;
    }
    cout<<sum<<endl;
    return 0;
}