UnionFind.js

UnionFind.js is a optimized implementation of the Union–Find (Disjoint Set Union) data structure for JavaScript.
It supports union by size and path halving for near-constant-time performance in practical use cases.

Features

• Union–Find / Disjoint Set Union with union by size and path halving
• Single Int32Array storage for maximum memory efficiency
• Amortized O(α(N)) performance (inverse Ackermann function)
• Zero allocations in hot paths
• reset() method for instant reuse without GC churn
• Works in Node.js and browsers

Installation

You can install UnionFind.js via npm:

npm install @rawify/unionfind

Or with yarn:

yarn add @rawify/unionfind

Alternatively, download or clone the repository:

git clone https://github.com/rawify/UnionFind.js

Usage

In Node.js:

const UnionFind = require('@rawify/unionfind');

Or ES modules:

import UnionFind from '@rawify/unionfind';

Creating a UnionFind instance

// Create a UnionFind for elements 0..9
let uf = new UnionFind(10);

find(x)

Finds the representative (root) of the set containing x.

uf.find(3); // returns root index of set containing 3

union(a, b)

Merges the sets containing a and b. Returns true if merged, false if already in the same set.

uf.union(1, 2); // merges sets containing 1 and 2

connected(a, b)

Checks whether a and b are in the same set.

uf.connected(1, 2); // true

sizeOf(x)

Returns the size of the set containing x.

uf.sizeOf(1); // 3

count()

Returns the number of disjoint sets.

uf.count(); // 7

reset()

Resets the structure to all singletons without reallocating.

uf.reset();

length

Returns the number of elements tracked.

uf.length; // 10

Example

const uf = new UnionFind(5);

uf.union(0, 1);
uf.union(3, 4);

console.log(uf.connected(0, 1)); // true
console.log(uf.connected(1, 2)); // false

console.log(uf.sizeOf(0)); // 2
console.log(uf.count());   // 3

uf.union(1, 4);
console.log(uf.connected(0, 3)); // true

Performance Notes

• Typed arrays keep memory compact and make find/union JIT-friendly.
• Path halving improves cache locality and minimizes pointer chasing.
• Avoids per-call allocations for maximum throughput in tight loops.
• Use reset() to reuse the structure without creating garbage.

Coding Style

As with every library I publish, UnionFind.js is written to be as small and efficient as possible after compression with Google Closure Compiler in advanced mode. Please preserve this style if you plan to extend the library.

Building the library

After cloning the Git repository run:

npm install
npm run build

Run a test

Testing the source against the shipped test suite is as easy as:

npm run test

Copyright and Licensing

Copyright (c) 2025, Robert Eisele Licensed under the MIT license.