Nerdy Poly Millionaires

    @manubb/union-find

    1.0.2 • Public • Published

    Union-Find

    A JS implementation of disjoint-set data structure for node and browsers.

    Installation

    The library is available as a npm package:

    npm install @manubb/union-find
    

    Examples

    Examples directory contains implementations of:

    Examples can be run with:

    npm run example:components
    npm run example:hk
    npm run example:kruskal
    

    API

    The library uses trees to encode sets. It exposes three functions.

    makeSet

    makeSet();

    returns an object representing a set containing one element. It has two properties: parent and rank. You can then safely add other properties that suit to your needs.

    Note that you can also use your own custom function that should return an object obj with:

    obj.rank === 0
    obj.parent === obj

    At any time, you can check if obj is the root of a tree with:

    obj.parent === obj

    find

    find(obj)

    returns the root of the tree that contains obj. Checking if two objects belong to the same set can be done with:

    find(obj1) === find(obj2)

    union

    union(obj1, obj2)

    merges the sets containing obj1 and obj2 and returns undefined.

    Complexity

    makeSet run in constant time. If n is the total number of elements, find and union run in amortized time O(α(n)) where α is the inverse Ackermann function. It is a very slowly increasing function: α(10^35164)=5. For all practical purposes, one can consider that find and union run in constant amortized time.

    Usage

    import { makeSet, find, union } from '@manubb/union-find';

    or

    const { makeSet, find, union } = require('@manubb/union-find');

    Install

    npm i @manubb/union-find

    DownloadsWeekly Downloads

    4

    Version

    1.0.2

    License

    MIT

    Unpacked Size

    9.63 kB

    Total Files

    11

    Last publish

    Collaborators

    • manubb