并查集

增删改查时间复杂度为O(1)的结构目前学到的有哈希表跟并查集

什么是并查集？

1)有若干个样本a、b、c、d…类型假设是V

2)在并查集中一开始认为每个样本都在单独的集合里

3)用户可以在任何时候调用如下两个方法：

• boolean isSameSet(V x, V y)：查询样本x和样本y是否属于一个集合
• void union(V x, V y) ：把x和y各自所在集合的所有样本合并成一个集合

4)isSameSet和union方法的代价越低越好，最好是O(1)

补充

1）每个节点都有一条往上指的指针

2)节点a往上找到的头节点，叫做a所在集合的代表节点

3)查询x和y是否属于同一个集合，就是看看找到的代表节点是不是一个

4)把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂
在大集合的代表点的下方即可

并查集的优化

1)节点往上找代表点的过程，把沿途的链变成扁平的

2)小集合挂在大集合的下面

3)如果方法调用很频繁，那么单次调用的代价为O(1)，两个方法都如此

并查集的应用

1. 解决两大块区域的合并问题
2. 常用在图等领域中

核心代码&&详细注释

package com.harrison.class10;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class Code01_UnionFind {
	// 自定义V类型，每个样本value外面包裹一层
	public static class Node<V>{
		V value;
		
		public Node(V v) {
			value=v;
		}
	}
	
	public static class UnionSet<V>{
		// 在nodes表里面，任何一个样本value都一一对应一个结点
		// 且初始化以后，永远不会有改动，只是记下对应关系
		public HashMap<V, Node<V>> nodes;
		// 每一个结点和自己的父结点都一一对应，记录在parents表里面
		public HashMap<Node<V>, Node<V>> parents;
		// 只有一个点，且这个点是集合的代表点
		public HashMap<Node<V>, Integer> sizeMap;
		
		public UnionSet(List<V> values) {// 用户把所有样本一次性给出
			for(V cur:values) {
				// 将每一个样本value都在外面包裹一层形成node
				Node<V> node=new Node<>(cur);
				// 记下对应关系，之后永不改变
				nodes.put(cur, node);
				// 因为一开始每一个样本只有自己，所以父结点仍然是自己
				parents.put(node, node);
				// 因为一开始每一个点都是代表点，所以集合大小就是1
				sizeMap.put(node, 1);
			}
		}
		
		// 从点cur开始，一直往上找，找到不能再往上的代表点，返回
		// 沿途所有结点都放入一个容器里（容器可以不是栈），目的是记下沿途路径
		public Node<V> findFather(Node<V> cur){
			Stack<Node<V>> path=new Stack<>();
			while(cur!=parents.get(cur)) {
				path.push(cur);
				cur=parents.get(cur);
			}
			// 跳出上面的循环后,cur一定指向代表点
			// 返回代表点之前，把沿途所有结点的父结点都改成代表点
			// 重要优化就体现在这，将链扁平化
			while(!path.isEmpty()) {
				parents.put(path.pop(), cur);
			}
			return cur;
		}
		
		public boolean isSameSet(V a,V b) {
			// 如果两个样本中有任何一个样本没有在nodes表里初始化，
			// 就必然不会在同一个集合里
			if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
				return false;
			}
			// if没中，说明两个样本都在nodes表里登记了
			// 通过样本找它所在集合的代表点，如果两个代表点的内存地址一样
			// 就说明是在同一个集合
			return findFather(nodes.get(a))==findFather(nodes.get(b));
		}
		
		// 注意：是a样本所在的整个集合 和 b样本所在的整个集合 进行合并
		public void union(V a,V b) {
			// 没有登记，无法合并
			if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
				return ;
			}
			// 登记了的话，找到自己所在集合的代表点
			Node<V> aHead=findFather(nodes.get(a));
			Node<V> bHead=findFather(nodes.get(b));
			// 只有两个代表点内存地址不一样才需要合并
			// 否则，说明这两个代表点所代表的两个集合本来就合并好了
			if(aHead!=bHead) {
				// 分别求得两个集合的的大小
				int aSetSize=sizeMap.get(aHead);
				int bSetSize=sizeMap.get(bHead);
				Node<V> big=aSetSize>=bSetSize?aHead:bHead;
				Node<V> small=big==aHead?bHead:aHead;
				// 小集合挂在大集合的下面
				// 直接把小集合头节点的父结点改为大集合的头节点
				parents.put(small, big);
				// 所以大集合的大小就变为两个集合大小相加
				sizeMap.put(big, aSetSize+bSetSize);
				// 小集合头节点不在作为代表点了，所以删掉在sizeMap里的记录
				sizeMap.remove(small);
			}
		}
	}
}