tessl/npm-mnemonist

Curated collection of efficient data structures for JavaScript/TypeScript applications.

—

Pending

Quality

Pending

Does it follow best practices?

Impact

Pending

No eval scenarios have been run

Securityby

Pending

The risk profile of this skill

Overview

Eval results

Files

Heaps & Priority Queues

Name: tessl/npm-mnemonist
Author: tessl

High-performance priority queue implementations for efficient minimum/maximum element access with logarithmic insertion and removal operations.

Capabilities

Basic Heap

Binary heap implementation providing O(log n) insertion and deletion with O(1) peek operations.

/**
 * Binary heap (min-heap by default) with configurable comparison function
 * @param comparator Optional comparison function for custom ordering
 */
function Heap<T>(comparator?: (a: T, b: T) => number): Heap<T>;

interface Heap<T> {
  /** Number of items in the heap */
  readonly size: number;
  
  /** Add item to the heap, returns new size */
  push(item: T): number;
  
  /** Returns the minimum item without removing it */
  peek(): T | undefined;
  
  /** Removes and returns the minimum item */
  pop(): T | undefined;
  
  /** Pops heap then pushes new item, returns popped item */
  replace(item: T): T | undefined;
  
  /** Pushes item then pops heap, returns popped item */
  pushpop(item: T): T | undefined;
  
  /** Returns sorted array of all items (non-destructive) */
  toArray(): Array<T>;
  
  /** Returns sorted array and clears the heap */
  consume(): Array<T>;
  
  /** Removes all items from the heap */
  clear(): void;
  
  /** Returns representation for debugging */
  inspect(): any;
}

Usage Examples:

import {Heap} from "mnemonist";

// Basic min-heap
const minHeap = new Heap<number>();
minHeap.push(5, 2, 8, 1, 9);
console.log(minHeap.peek()); // 1
console.log(minHeap.pop());  // 1
console.log(minHeap.size);   // 4

// Custom priority heap
interface Task { name: string; priority: number; }
const taskHeap = new Heap<Task>((a, b) => a.priority - b.priority);
taskHeap.push({name: "urgent", priority: 1});
taskHeap.push({name: "normal", priority: 5});
console.log(taskHeap.peek().name); // "urgent"

// Efficient operations
const item = minHeap.pushpop(3); // Push 3, then pop minimum
const replaced = minHeap.replace(7); // Pop minimum, then push 7

Min Heap & Max Heap

Specialized heap variants for explicit minimum or maximum ordering.

/**
 * Min-heap: smallest item at root (alias for default Heap behavior)
 */
function MinHeap<T>(comparator?: (a: T, b: T) => number): MinHeap<T>;

/**
 * Max-heap: largest item at root
 */
function MaxHeap<T>(comparator?: (a: T, b: T) => number): MaxHeap<T>;

Usage Examples:

import {MinHeap, MaxHeap} from "mnemonist";

const minHeap = new MinHeap<number>();
const maxHeap = new MaxHeap<number>();

[5, 2, 8, 1, 9].forEach(n => {
  minHeap.push(n);
  maxHeap.push(n);
});

console.log(minHeap.peek()); // 1 (smallest)
console.log(maxHeap.peek()); // 9 (largest)

Heap Static Methods

Factory methods on the Heap class.

/**
 * Create heap from iterable (static method on Heap class)
 */
static from<T>(
  iterable: Iterable<T> | {[key: string]: T},
  comparator?: (a: T, b: T) => number
): Heap<T>;

Heap Utility Functions

Standalone utility functions for finding k smallest/largest elements efficiently.

/**
 * Find n smallest items from iterable using heap
 */
function nsmallest<T>(n: number, values: Iterable<T>): Array<T>;
function nsmallest<T>(
  comparator: (a: T, b: T) => number,
  n: number,
  values: Iterable<T>
): Array<T>;

/**
 * Find n largest items from iterable using heap
 */
function nlargest<T>(n: number, values: Iterable<T>): Array<T>;
function nlargest<T>(
  comparator: (a: T, b: T) => number,
  n: number,
  values: Iterable<T>
): Array<T>;

Usage Examples:

import {Heap} from "mnemonist";

// Create from array
const heap = Heap.from([5, 2, 8, 1, 9]);
console.log(heap.peek()); // 1

Usage Examples:

import {nsmallest, nlargest} from "mnemonist";

// Find smallest/largest items efficiently
const numbers = [15, 3, 8, 1, 12, 7, 4, 9];
const smallest3 = nsmallest(3, numbers); // [1, 3, 4]
const largest3 = nlargest(3, numbers);   // [15, 12, 9]

// With custom comparator
const people = [{name: "Alice", age: 30}, {name: "Bob", age: 25}];
const youngest2 = nsmallest((a, b) => a.age - b.age, 2, people);

Fibonacci Heap

Advanced heap with better amortized time complexity for decrease-key operations.

/**
 * Fibonacci heap providing O(1) amortized insertion and decrease-key
 * @param comparator Optional comparison function for custom ordering
 */
function FibonacciHeap<T>(comparator?: (a: T, b: T) => number): FibonacciHeap<T>;

interface FibonacciHeap<T> {
  /** Number of items in the heap */
  readonly size: number;
  
  /** Add item to the heap, returns new size */
  push(item: T): number;
  
  /** Returns the minimum item without removing it */
  peek(): T | undefined;
  
  /** Removes and returns the minimum item */
  pop(): T | undefined;
  
  /** Removes all items from the heap */
  clear(): void;
  
  /** Returns representation for debugging */
  inspect(): any;
}

Usage Examples:

import {FibonacciHeap, MinFibonacciHeap, MaxFibonacciHeap} from "mnemonist";

// Basic fibonacci heap (min-heap)
const fibHeap = new FibonacciHeap<number>();
fibHeap.push(5, 2, 8, 1);
console.log(fibHeap.pop()); // 1

// Max fibonacci heap
const maxFibHeap = new MaxFibonacciHeap<number>();
maxFibHeap.push(5, 2, 8, 1);
console.log(maxFibHeap.pop()); // 8

// Create from iterable
const heap = FibonacciHeap.from([3, 1, 4, 1, 5]);

Performance Notes:

Better for applications with many insertions and few deletions
O(1) amortized insert vs O(log n) for binary heap
O(log n) amortized delete-min (same as binary heap)
More memory overhead than basic heap

Fixed Reverse Heap

Fixed-capacity heap optimized for finding k smallest/largest items from streaming data.

/**
 * Fixed-capacity heap that maintains k best items
 * @param ArrayClass Array constructor for backing storage
 * @param comparator Optional comparison function
 * @param capacity Maximum number of items to store
 */
function FixedReverseHeap<T>(
  ArrayClass: ArrayConstructor,
  comparator: (a: T, b: T) => number,
  capacity: number
): FixedReverseHeap<T>;

function FixedReverseHeap<T>(
  ArrayClass: ArrayConstructor,
  capacity: number
): FixedReverseHeap<T>;

interface FixedReverseHeap<T> {
  /** Maximum capacity of the heap */
  readonly capacity: number;
  
  /** Current number of items in the heap */
  readonly size: number;
  
  /** Add item if space available, or replace worst item if full */
  push(item: T): number;
  
  /** Returns sorted array and clears the heap */
  consume(): Array<T>;
  
  /** Returns sorted array (non-destructive) */
  toArray(): Array<T>;
  
  /** Removes all items from the heap */
  clear(): void;
  
  /** Returns representation for debugging */
  inspect(): any;
}

Usage Examples:

import {FixedReverseHeap} from "mnemonist";

// Find 5 smallest numbers from stream
const kSmallest = new FixedReverseHeap(Array, 5);

// Process streaming data
[8, 3, 15, 1, 12, 7, 4, 9, 2, 11].forEach(num => {
  kSmallest.push(num);
});

console.log(kSmallest.toArray()); // [1, 2, 3, 4, 7] (5 smallest)

// Find largest items with custom comparator  
const kLargest = new FixedReverseHeap(
  Array,
  (a, b) => b - a, // Reverse comparator for largest
  3
);

[8, 3, 15, 1, 12].forEach(num => kLargest.push(num));
console.log(kLargest.toArray()); // [15, 12, 8] (3 largest)

// Using typed arrays for performance
const typedHeap = new FixedReverseHeap(Float32Array, 100);

Performance Notes:

O(log k) insertion where k is capacity
O(1) space beyond the k items stored
Ideal for "top-k" problems with streaming data
Automatically handles capacity management

Low-Level Heap Operations

Direct array-based heap operations for advanced use cases.

/**
 * Low-level heap operations on raw arrays
 */
namespace HeapOperations {
  function push<T>(comparator: (a: T, b: T) => number, heap: Array<T>, item: T): void;
  function pop<T>(comparator: (a: T, b: T) => number, heap: Array<T>): T;
  function replace<T>(comparator: (a: T, b: T) => number, heap: Array<T>, item: T): T;
  function pushpop<T>(comparator: (a: T, b: T) => number, heap: Array<T>, item: T): T;
  function heapify<T>(comparator: (a: T, b: T) => number, array: Array<T>): void;
  function consume<T>(comparator: (a: T, b: T) => number, heap: Array<T>): Array<T>;
}

Types

/**
 * Comparison function type used by all heap implementations
 * Should return: negative if a < b, zero if a === b, positive if a > b
 */
type HeapComparator<T> = (a: T, b: T) => number;

/**
 * Array constructor types supported by FixedReverseHeap
 */
type ArrayConstructor = 
  | ArrayConstructor
  | Int8ArrayConstructor
  | Uint8ArrayConstructor
  | Int16ArrayConstructor
  | Uint16ArrayConstructor
  | Int32ArrayConstructor
  | Uint32ArrayConstructor
  | Float32ArrayConstructor
  | Float64ArrayConstructor;

Performance Characteristics

Operation	Basic Heap	Fibonacci Heap	Fixed Reverse Heap
Insert	O(log n)	O(1) amortized	O(log k)
Extract Min	O(log n)	O(log n) amortized	N/A
Peek	O(1)	O(1)	N/A
Build from array	O(n)	O(n)	O(k log k)
Space	O(n)	O(n)	O(k)

Where n is the total number of elements and k is the fixed capacity.

Choosing the Right Heap

Basic Heap: General-purpose priority queue with good performance
Fibonacci Heap: When you need many insertions with occasional decreases of priorities
Fixed Reverse Heap: For "top-k" problems or when memory is constrained
Max variants: When you need largest-first ordering instead of smallest-first