并查集
增删改查时间复杂度为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)，两个方法都如此
并查集的应用
解决两大块区域的合并问题
常用在图等领域中
核心代码&&详细注释
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); } } } }
