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