第7章 神奇的树

第1节 开启“树”之旅

不含回路的连通无向图。

现实中的族谱、操作系统中的“目录”。

树的相关概念：略略略

第2节 二叉树

二叉树是每个节点最多有两个儿子的树。

满二叉树、完全二叉树（满二叉树的一部分）

完全二叉树存储规律：只要用一个一维数组就可以存储完全二叉树，将完全二叉树进行从上到下，从左到右编号，，可以发现如果父节点的编号是k,那么它的子节点的编号是2k和2k+1。若子节点是x，父节点就是x/2。

第3节 堆–神奇的优先队列

堆是一种特殊的完全二叉树，所有的父节点比子节点小。称为最小堆。如果所有的父节点比子节点大，则称为最大堆。

最小堆的操作：

void siftdown(int i) { //从i向下调整(i插入一个数后)
    int flag = 0;
    int t;
    while(i*2<=n && flag==0) {
      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) {
        int k = h[t];
        h[t] = h[i];
        h[i] = k;
        i = t;
      }else {
        flag = 1;
      }
    }
  }

向上调整（插入末尾）

void siftup(int i) {//从i向上调整
    int flag = 0;
    if(i==1) return;
    while(i!=1 && flag==0) {
      if(h[i]<h[i/2]) {
        int kk = h[i];
        h[i] = h[i/2];
        h[i/2]=kk;
      }else {
        flag = 1;
      }
      i = i/2;
    }
  }

建立堆

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

完整的对排序：

package ch7;

import java.util.Scanner;

public class Test1 {

  int[] h = new int[101];
  int n;
  void siftdown(int i) { //从i向下调整
    int flag = 0;
    int t;
    while(i*2<=n && flag==0) {
      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) {
        int k = h[t];
        h[t] = h[i];
        h[i] = k;
        i = t;
      }else {
        flag = 1;
      }
    }
  }
  
  void siftup(int i) {//从i向上调整
    int flag = 0;
    if(i==1) return;
    while(i!=1 && flag==0) {
      if(h[i]<h[i/2]) {
        int kk = h[i];
        h[i] = h[i/2];
        h[i/2]=kk;
      }else {
        flag = 1;
      }
      i = i/2;
    }
  }
  
  
  //建立堆
  void create() {
    for(int i=n/2;i>=1;i--) {
      siftdown(i);
    }
  }

  
  //堆排序，每次删除顶部元素
  int deletetop() {
    int t;
    t = h[1];
    h[1] = h[n];
    n--;
    siftdown(1);
    return t;
  }
  
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    Test1 t1 = new Test1();
    for(int i=1;i<=num;i++) {
      t1.h[i] = sc.nextInt();
    }
    t1.n = num;
    t1.create();
    for(int i=1;i<=num;i++) {
      System.out.print(t1.deletetop()+ " ");
    }
  }  
}

另一种堆排序的方法：建立最大堆，h[1]是最大的数，每次把h[1]和h[n]交换，h[n]就是最大的数，然后n–，在从h[1]向下调整。直到堆只剩下一个数。（最大堆和最小堆类似，只是最大堆的父结点大于子节点）

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

第4节 擒贼先擒王–并查集

有n个强盗，m条线索，每条线索给出的是x号强盗和y号强盗是同伙，求一共有多少个犯罪团伙。

//测试数据
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
//结果3

package ch7;

import java.util.Scanner;

public class Test2 {
  int[] f = new int[1000];
  int n,m,k,sum;
  //初始化f
  void init() {
    for(int i=1;i<=n;i++) {
      f[i] = i;
    }
  }
  //找爹的递归函数
  int getf(int v) {
    if(f[v]==v) {
      return v;
    }else {
      f[v] = getf(f[v]);//路径压缩，每次函数返回时，顺便将遇到的人的Boss改为最后找到的祖宗编号
      return f[v];
    }
  }
  //合并子集（同伙）
  void merge(int v,int u) {
    int t1 = getf(v);
    int t2 = getf(u);
    if(t1 != t2) {
      f[t2] = t1; //靠左原则，合并到左边
    }
  }
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    Test2 t2 = new Test2();
    t2.n = sc.nextInt();
    t2.init();

    int m = sc.nextInt();
    for(int i=1;i<=m;i++) {
      int x = sc.nextInt();
      int y = sc.nextInt();
      t2.merge(x, y);
    }
    
    for(int i=1;i<=t2.n;i++) {
      if(t2.f[i]==i) {
        t2.sum++;
      }
    }
    System.out.println(t2.sum);
    
  }
}