Package dsa

Class QuickUnionUF

java.lang.Object
dsa.QuickUnionUF
All Implemented Interfaces:
UF
public class QuickUnionUF extends Object implements UF
This data type provides an implementation of the Union Find (UF) API in which the count operation runs in constant time, whereas the find, connected, and union operations run in logarithmic time in the average case.

  • Constructor Summary

    Constructors
    Constructor
    Description
    QuickUnionUF(int n)
    Constructs an empty UF data structure with n sites.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    connected(int p, int q)
    Returns true if sites p and q belong to the same component, and false otherwise.
    int
    count()
    Returns the number of components.
    int
    find(int p)
    Returns the canonical site of the component containing site p.
    static void
    main(String[] args)
    Unit tests the data type.
    void
    union(int p, int q)
    Connects sites p and q.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • QuickUnionUF

      public QuickUnionUF(int n)
      Constructs an empty UF data structure with n sites.
      Parameters:
      n - the number of sites.

  • Method Details

    • find

      public int find(int p)
      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()
      Returns the number of components.
      Specified by:
      count in interface UF
      Returns:
      the number of components.

    • connected

      public boolean connected(int p, int q)
      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)
      Connects sites p and q.
      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.