第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); } }
