Joint search set structure

Union checking set

The time complexity of adding, deleting, modifying and checking is O(1) At present, we have learned the structure of hash table and parallel query set

What is juxtaposition ？

1) There are several samples a、b、c、d… The type assumption is V

2) In the parallel search set, it was initially thought that each sample was in a separate set

3) The user can call the following two methods at any time ：

• boolean isSameSet(V x, V y)： Query sample x And the sample y Whether it belongs to a collection
• void union(V x, V y) ： hold x and y All samples in their respective sets are combined into one set

4)isSameSet and union The lower the cost of the method, the better , It is best to O(1)

Add

1） Each node has a pointer pointing up

2) node a Find the header node up , be called a The representative node of the set

3) Inquire about x and y Whether they belong to the same set , Is to see if the representative node found is a

4) hold x and y All points of the respective set are merged into a set , Just need a small set of representative points to hang
Just below the representative points of the large set

And search set optimization

1) The process of nodes looking for representative points up , Turn the chain along the way into a flat

2) The small collection hangs under the large collection

3) If method calls are frequent , Then the cost of a single call is O(1), Both ways

And look up the application of the set

1. Solve the problem of merging two large areas
2. It is often used in fields such as graphs

Core code && Detailed notes

package com.harrison.class10;

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

public class Code01_UnionFind {
    
	//  Customize V type , Each sample value Wrap a layer outside 
	public static class Node<V>{
    
		V value;
		
		public Node(V v) {
    
			value=v;
		}
	}
	
	public static class UnionSet<V>{
    
		//  stay nodes Inside the watch , Any sample value Each one corresponds to a node 
		//  And after initialization , There will never be any change , Just write down the correspondence 
		public HashMap<V, Node<V>> nodes;
		//  Each node corresponds to its parent node one by one , Recorded in the parents Inside the watch 
		public HashMap<Node<V>, Node<V>> parents;
		//  There is only one point , And this point is the representative point of the set 
		public HashMap<Node<V>, Integer> sizeMap;
		
		public UnionSet(List<V> values) {
    //  The user gives all samples at one time 
			for(V cur:values) {
    
				//  Take each sample value All wrapped in a layer to form node
				Node<V> node=new Node<>(cur);
				//  Write down the correspondence , Never change after 
				nodes.put(cur, node);
				//  Because in the beginning, each sample only had its own , So the parent node is still itself 
				parents.put(node, node);
				//  Because in the beginning, every point is a representative point , So the set size is 1
				sizeMap.put(node, 1);
			}
		}
		
		//  From the point of cur Start , Keep looking up , Find a representative point that can't go up , return 
		//  All nodes along the way are put into a container （ Containers can not be stacks ）, The purpose is to write down the path 
		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);
			}
			//  After jumping out of the above loop ,cur It must point to the representative point 
			//  Before returning to the representative point , Change the parent nodes of all nodes along the way to representative points 
			//  Important optimization is reflected in this , Flatten the chain 
			while(!path.isEmpty()) {
    
				parents.put(path.pop(), cur);
			}
			return cur;
		}
		
		public boolean isSameSet(V a,V b) {
    
			//  If either of the two samples is not in nodes Table initialization ,
			//  It must not be in the same set 
			if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
    
				return false;
			}
			// if Missed , It means that both samples are nodes It's registered in the form 
			//  Find the representative point of the set through the sample , If the memory addresses of two representative points are the same 
			//  It means that it is in the same set 
			return findFather(nodes.get(a))==findFather(nodes.get(b));
		}
		
		//  Be careful ： yes a The entire set of samples   and  b The entire set of samples   A merger 
		public void union(V a,V b) {
    
			//  Not registered , Can't merge 
			if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
    
				return ;
			}
			//  If registered , Find the representative point of your set 
			Node<V> aHead=findFather(nodes.get(a));
			Node<V> bHead=findFather(nodes.get(b));
			//  Only two representative points with different memory addresses need to be merged 
			//  otherwise , It shows that the two sets represented by these two representative points are already merged 
			if(aHead!=bHead) {
    
				//  Find the size of two sets respectively 
				int aSetSize=sizeMap.get(aHead);
				int bSetSize=sizeMap.get(bHead);
				Node<V> big=aSetSize>=bSetSize?aHead:bHead;
				Node<V> small=big==aHead?bHead:aHead;
				//  The small collection hangs under the large collection 
				//  Directly change the parent node of the head node of a small set into the head node of a large set 
				parents.put(small, big);
				//  So the size of a large set becomes the sum of the sizes of two sets 
				sizeMap.put(big, aSetSize+bSetSize);
				//  The small set head node is no longer used as a representative point , So delete in sizeMap The records in 
				sizeMap.remove(small);
			}
		}
	}
}