/Disjoint-Sets-Data-Structure

Efficient implementation of the Disjoint Sets data structure in Python

Primary LanguagePythonMIT LicenseMIT

Disjoint Sets Data Structure

This is an efficient implementation of the Disjoint Sets data structure, written in Python.

Uses Trees, Union by Rank Heuristic, and Path Compression Heuristic.

Uses 1-based indexing of arrays.

When both union by rank heuristic and path compression heuristic are used, the average running time of each operation is nearly constant.

The code includes examples.