Package dsa

Class QuickUnionUF

  • All Implemented Interfaces:
    UF

    public class QuickUnionUF
    extends Object
    implements UF
    This data type provides an implementation of the UF API in which the find and union operations are efficient (run in logarithmic time) in the average case.
    • Constructor Detail

      • QuickUnionUF

        public QuickUnionUF​(int n)
        Constructs an empty union-find data structure with n sites.
        Parameters:
        n - the number of sites.
    • Method Detail

      • find

        public int find​(int p)
        Description copied from interface: UF
        Returns the canonical site of the component containing site p.
        Specified by:
        find in interface UF
        Parameters:
        p - a site.
        Returns:
        the canonical site of the component containing site p.
      • count

        public int count()
        Description copied from interface: UF
        Returns the number of components.
        Specified by:
        count in interface UF
        Returns:
        the number of components.
      • connected

        public boolean connected​(int p,
                                 int q)
        Description copied from interface: UF
        Returns true if sites p and q belong to the same component, and false otherwise.
        Specified by:
        connected in interface UF
        Parameters:
        p - one site.
        q - the other site.
        Returns:
        true if sites p and q belong to the same component, and false otherwise.
      • union

        public void union​(int p,
                          int q)
        Description copied from interface: UF
        Connects sites p and q if they are not already connected.
        Specified by:
        union in interface UF
        Parameters:
        p - one site.
        q - the other site.
      • main

        public static void main​(String[] args)
        Unit tests the data type.
        Parameters:
        args - the command-line arguments.