Class UnionFind<T>

  • Type Parameters:
    T - element type

    public class UnionFind<T>
    extends java.lang.Object
    An implementation of Union Find data structure. Union Find is a disjoint-set data structure. It supports two operations: finding the set a specific element is in, and merging two sets. The implementation uses union by rank and path compression to achieve an amortized cost of O(a(n)) per operation where a is the inverse Ackermann function. UnionFind uses the hashCode and equals method of the elements it operates on.
    Since:
    Feb 10, 2010
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Map<T,​T> parentMap  
      private java.util.Map<T,​java.lang.Integer> rankMap  
    • Constructor Summary

      Constructors 
      Constructor Description
      UnionFind​(java.util.Set<T> elements)
      Creates a UnionFind instance with all the elements in separate sets.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addElement​(T element)
      Adds a new element to the data structure in its own set.
      T find​(T element)
      Returns the representative element of the set that element is in.
      protected java.util.Map<T,​T> getParentMap()  
      protected java.util.Map<T,​java.lang.Integer> getRankMap()  
      void union​(T element1, T element2)
      Merges the sets which contain element1 and element2.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • parentMap

        private java.util.Map<T,​T> parentMap
      • rankMap

        private java.util.Map<T,​java.lang.Integer> rankMap
    • Constructor Detail

      • UnionFind

        public UnionFind​(java.util.Set<T> elements)
        Creates a UnionFind instance with all the elements in separate sets.
        Parameters:
        elements - the initial elements to include (each element in a singleton set).
    • Method Detail

      • addElement

        public void addElement​(T element)
        Adds a new element to the data structure in its own set.
        Parameters:
        element - The element to add.
      • getParentMap

        protected java.util.Map<T,​T> getParentMap()
        Returns:
        map from element to parent element
      • getRankMap

        protected java.util.Map<T,​java.lang.Integer> getRankMap()
        Returns:
        map from element to rank
      • find

        public T find​(T element)
        Returns the representative element of the set that element is in.
        Parameters:
        element - The element to find.
        Returns:
        The element representing the set the element is in.
      • union

        public void union​(T element1,
                          T element2)
        Merges the sets which contain element1 and element2.
        Parameters:
        element1 - The first element to union.
        element2 - The second element to union.