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

Package detail

@rawify/unionfind

readme