DataStructures
Class DisjSetsFast

java.lang.Object
  |
  +--DataStructures.DisjSetsFast

public class DisjSetsFast

extends java.lang.Object

Disjoint set class, using union by rank and path compression. Elements in the set are numbered starting at 0.

Constructor Summary

DisjSetsFast(int numElements)
Construct the disjoint sets object.

Method Summary

int	find(int x) Perform a find with path compression.
static void	main(java.lang.String[] args)
void	union(int root1, int root2) Union two disjoint sets using the height heuristic.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjSetsFast

public DisjSetsFast(int numElements)

Construct the disjoint sets object.

Parameters:

numElements - the initial number of disjoint sets.

Method Detail

union

public void union(int root1,
                  int root2)

Union two disjoint sets using the height heuristic. For simplicity, we assume root1 and root2 are distinct and represent set names.

Parameters:

root1 - the root of set 1.

root2 - the root of set 2.

find

public int find(int x)

Perform a find with path compression. Error checks omitted again for simplicity.

Parameters:

x - the element being searched for.

Returns:

the set containing x.

main

public static void main(java.lang.String[] args)