Package algs15

Class WeightedUF

java.lang.Object
algs15.WeightedUF
All Implemented Interfaces:
UF
public class WeightedUF extends Object implements UF
The UF class represents a union-find data data structure. It supports the union and find operations, along with a method for determining the number of disjoint sets.

This implementation uses weighted quick union. Creating a data structure with N objects takes linear time. Afterwards, all operations are logarithmic worst-case time.

For additional documentation, see Section 1.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private int
    count
     
    private int[]
    id
     
    private int[]
    sz
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    WeightedUF(int N)
    Create an empty union find data structure with N isolated sets.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    connected(int p, int q)
    Are objects p and q in the same set?
    int
    count()
    Return the number of disjoint sets.
    int
    find(int p)
    Return the id of component corresponding to object p.
    static void
    main(String[] args)
     
    void
    toGraphviz()
     
    String
    toString()
     
    void
    union(int p, int q)
    Replace sets containing p and q with their union.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • id

      private int[] id

    • sz

      private int[] sz

    • count

      private int count

  • Constructor Details

    • WeightedUF

      public WeightedUF(int N)
      Create an empty union find data structure with N isolated sets.

  • Method Details

    • count

      public int count()
      Return the number of disjoint sets.
      Specified by:
      count in interface UF

    • connected

      public boolean connected(int p, int q)
      Are objects p and q in the same set?
      Specified by:
      connected in interface UF

    • find

      public int find(int p)
      Return the id of component corresponding to object p.
      Specified by:
      find in interface UF

    • union

      public void union(int p, int q)
      Replace sets containing p and q with their union.
      Specified by:
      union in interface UF

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • toGraphviz

      public void toGraphviz()
      Specified by:
      toGraphviz in interface UF

    • main

      public static void main(String[] args)