Class Heap<E, R>

Binary heap with pluggable comparator; supports fast insertion and removal of the top element.

Remarks

Time O(1), Space O(1)

Example

// basic Heap creation and add operation
 // Create a min heap (default)
    const minHeap = new Heap([5, 3, 7, 1, 9, 2]);

    // Verify size
    console.log(minHeap.size); // 6;

    // Add new element
    minHeap.add(4);
    console.log(minHeap.size); // 7;

    // Min heap property: smallest element at root
    const min = minHeap.peek();
    console.log(min); // 1;

Example

// Heap with custom comparator (MaxHeap behavior)
 interface Task {
      id: number;
      priority: number;
      name: string;
    }

    // Custom comparator for max heap behavior (higher priority first)
    const tasks: Task[] = [
      { id: 1, priority: 5, name: 'Email' },
      { id: 2, priority: 3, name: 'Chat' },
      { id: 3, priority: 8, name: 'Alert' }
    ];

    const maxHeap = new Heap(tasks, {
      comparator: (a: Task, b: Task) => b.priority - a.priority
    });

    console.log(maxHeap.size); // 3;

    // Peek returns highest priority task
    const topTask = maxHeap.peek();
    console.log(topTask?.priority); // 8;
    console.log(topTask?.name); // 'Alert';

Example

// Heap for event processing with priority
 interface Event {
      id: number;
      type: 'critical' | 'warning' | 'info';
      timestamp: number;
      message: string;
    }

    // Custom priority: critical > warning > info
    const priorityMap = { critical: 3, warning: 2, info: 1 };

    const eventHeap = new Heap<Event>([], {
      comparator: (a: Event, b: Event) => {
        const priorityA = priorityMap[a.type];
        const priorityB = priorityMap[b.type];
        return priorityB - priorityA; // Higher priority first
      }
    });

    // Add events in random order
    eventHeap.add({ id: 1, type: 'info', timestamp: 100, message: 'User logged in' });
    eventHeap.add({ id: 2, type: 'critical', timestamp: 101, message: 'Server down' });
    eventHeap.add({ id: 3, type: 'warning', timestamp: 102, message: 'High memory' });
    eventHeap.add({ id: 4, type: 'info', timestamp: 103, message: 'Cache cleared' });
    eventHeap.add({ id: 5, type: 'critical', timestamp: 104, message: 'Database error' });

    console.log(eventHeap.size); // 5;

    // Process events by priority (critical first)
    const processedOrder: Event[] = [];
    while (eventHeap.size > 0) {
      const event = eventHeap.poll();
      if (event) {
        processedOrder.push(event);
      }
    }

    // Verify critical events came first
    console.log(processedOrder[0].type); // 'critical';
    console.log(processedOrder[1].type); // 'critical';
    console.log(processedOrder[2].type); // 'warning';
    console.log(processedOrder[3].type); // 'info';
    console.log(processedOrder[4].type); // 'info';

    // Verify O(log n) operations
    const newHeap = new Heap<number>([5, 3, 7, 1]);

    // Add - O(log n)
    newHeap.add(2);
    console.log(newHeap.size); // 5;

    // Poll - O(log n)
    const removed = newHeap.poll();
    console.log(removed); // 1;

    // Peek - O(1)
    const top = newHeap.peek();
    console.log(top); // 2;

Example

// Use Heap to solve top k problems
 function topKElements(arr: number[], k: number): number[] {
      const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap
      arr.forEach(num => {
        heap.add(num);
        if (heap.size > k) heap.poll(); // Keep the heap size at K
      });
      return heap.toArray();
    }

    const numbers = [10, 30, 20, 5, 15, 25];
    console.log(topKElements(numbers, 3)); // [15, 10, 5];

Example

// Use Heap to dynamically maintain the median
 class MedianFinder {
      private low: MaxHeap<number>; // Max heap, stores the smaller half
      private high: MinHeap<number>; // Min heap, stores the larger half

      constructor() {
        this.low = new MaxHeap<number>([]);
        this.high = new MinHeap<number>([]);
      }

      addNum(num: number): void {
        if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num);
        else this.high.add(num);

        // Balance heaps
        if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!);
        else if (this.high.size > this.low.size) this.low.add(this.high.poll()!);
      }

      findMedian(): number {
        if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2;
        return this.low.peek()!;
      }
    }

    const medianFinder = new MedianFinder();
    medianFinder.addNum(10);
    console.log(medianFinder.findMedian()); // 10;
    medianFinder.addNum(20);
    console.log(medianFinder.findMedian()); // 15;
    medianFinder.addNum(30);
    console.log(medianFinder.findMedian()); // 20;
    medianFinder.addNum(40);
    console.log(medianFinder.findMedian()); // 25;
    medianFinder.addNum(50);
    console.log(medianFinder.findMedian()); // 30;

Example

// Use Heap for load balancing
 function loadBalance(requests: number[], servers: number): number[] {
      const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap
      const serverLoads = new Array(servers).fill(0);

      for (let i = 0; i < servers; i++) {
        serverHeap.add({ id: i, load: 0 });
      }

      requests.forEach(req => {
        const server = serverHeap.poll()!;
        serverLoads[server.id] += req;
        server.load += req;
        serverHeap.add(server); // The server after updating the load is re-entered into the heap
      });

      return serverLoads;
    }

    const requests = [5, 2, 8, 3, 7];
    console.log(loadBalance(requests, 3)); // [12, 8, 5];

Example

// Use Heap to schedule tasks
 type Task = [string, number];

    function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> {
      const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap
      const allocation = new Map<number, Task[]>();

      // Initialize the load on each machine
      for (let i = 0; i < machines; i++) {
        machineHeap.add({ id: i, load: 0 });
        allocation.set(i, []);
      }

      // Assign tasks
      tasks.forEach(([task, load]) => {
        const machine = machineHeap.poll()!;
        allocation.get(machine.id)!.push([task, load]);
        machine.load += load;
        machineHeap.add(machine); // The machine after updating the load is re-entered into the heap
      });

      return allocation;
    }

    const tasks: Task[] = [
      ['Task1', 3],
      ['Task2', 1],
      ['Task3', 2],
      ['Task4', 5],
      ['Task5', 4]
    ];
    const expectedMap = new Map<number, Task[]>();
    expectedMap.set(0, [
      ['Task1', 3],
      ['Task4', 5]
    ]);
    expectedMap.set(1, [
      ['Task2', 1],
      ['Task3', 2],
      ['Task5', 4]
    ]);
    console.log(scheduleTasks(tasks, 2)); // expectedMap;

Type Parameters

E = any
R = any
1. Complete Binary Tree: Heaps are typically complete binary trees, meaning every level is fully filled except possibly for the last level, which has nodes as far left as possible.
2. Heap Properties: Each node in a heap follows a specific order property, which varies depending on the type of heap: Max Heap: The value of each parent node is greater than or equal to the value of its children. Min Heap: The value of each parent node is less than or equal to the value of its children.
3. Root Node Access: In a heap, the largest element (in a max heap) or the smallest element (in a min heap) is always at the root of the tree.
4. Efficient Insertion and Deletion: Due to its structure, a heap allows for insertion and deletion operations in logarithmic time (O(log n)).
5. Managing Dynamic Data Sets: Heaps effectively manage dynamic data sets, especially when frequent access to the largest or smallest elements is required.
6. Non-linear Search: While a heap allows rapid access to its largest or smallest element, it is less efficient for other operations, such as searching for a specific element, as it is not designed for these tasks.
7. Efficient Sorting Algorithms: For example, heap sort. Heap sort uses the properties of a heap to sort elements.
8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prime's minimum-spanning tree algorithm, which use heaps to improve performance.

Hierarchy (view full)

IterableElementBase<E, R>
- Heap

Index

Constructors

constructor

new Heap<E, R>(elements?, options?): Heap<E, R>
Create a Heap and optionally bulk-insert elements.
Type Parameters
- E = any
- R = any
Parameters
- Optionalelements: Iterable<E | R, any, any> = []
  Iterable of elements (or raw values if toElementFn is set).
- Optionaloptions: HeapOptions<E, R>
  Options such as comparator and toElementFn.
Returns Heap<E, R>
New Heap instance.

Remarks
Time O(N), Space O(N)
Overrides IterableElementBase.constructor
- Defined in data-structures/heap/heap.ts:253

Properties

`Protected` `Optional`_toElementFn

_toElementFn?: ((rawElement: R) => E)

The converter used to transform a raw element (R) into a public element (E).

Remarks

Time O(1), Space O(1).

Accessors

comparator

get comparator(): Comparator<E>
Get the comparator used to order elements.

Returns Comparator<E>
Comparator function.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/heap/heap.ts:662

elements

get elements(): E[]
Get the backing array of the heap.

Returns E[]
Internal elements array.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/heap/heap.ts:272

leaf

get leaf(): undefined | E
Get the last leaf element.

Returns undefined | E
Last element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/heap/heap.ts:292

size

get size(): number
Get the number of elements.

Returns number
Heap size.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/heap/heap.ts:282

toElementFn

get toElementFn(): undefined | ((rawElement: R) => E)
Exposes the current toElementFn, if configured.

Returns undefined | ((rawElement: R) => E)
The converter function or undefined when not set.

Remarks
Time O(1), Space O(1).
Inherited from IterableElementBase.toElementFn
- Defined in data-structures/base/iterable-element-base.ts:47

Methods

`Protected`_createInstance

_createInstance(options?): this
(Protected) Create an empty instance of the same concrete class.
Parameters
- Optionaloptions: HeapOptions<E, R>
  Options to override comparator or toElementFn.
Returns this
A like-kind empty heap instance.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/heap/heap.ts:708

`Protected`_createLike

_createLike<EM, RM>(elements?, options?): Heap<EM, RM>
(Protected) Create a like-kind instance seeded by elements.
Type Parameters
- EM
- RM
Parameters
- Optionalelements: Iterable<EM, any, any> | Iterable<RM, any, any> = []
  Iterable of elements or raw values to seed.
- Optionaloptions: HeapOptions<EM, RM>
  Options forwarded to the constructor.
Returns Heap<EM, RM>
A like-kind heap instance.

Remarks
Time O(N log N), Space O(N)
- Defined in data-structures/heap/heap.ts:724

`Protected`_getIterator

_getIterator(): IterableIterator<E, any, any>
Internal iterator factory used by the default iterator.

Returns IterableIterator<E, any, any>
An iterator over elements.

Remarks
Implementations should yield in O(1) per element with O(1) extra space when possible.
Overrides IterableElementBase._getIterator
- Defined in data-structures/heap/heap.ts:666

`Protected`_spawnLike

_spawnLike<EM, RM>(options?): Heap<EM, RM>
(Protected) Spawn an empty like-kind heap instance.
Type Parameters
- EM
- RM
Parameters
- Optionaloptions: HeapOptions<EM, RM>
  Options forwarded to the constructor.
Returns Heap<EM, RM>
An empty like-kind heap instance.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/heap/heap.ts:741

[iterator]

[iterator](...args): IterableIterator<E, any, any>
Returns an iterator over the structure's elements.
Parameters
- Rest...args: unknown[]
  Optional iterator arguments forwarded to the internal iterator.
Returns IterableIterator<E, any, any>
An IterableIterator<E> that yields the elements in traversal order.

Remarks
Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.
Inherited from IterableElementBase.[iterator]
- Defined in data-structures/base/iterable-element-base.ts:60

add

add(element): boolean
Insert an element.
Parameters
- element: E
  Element to insert.
Returns boolean
True.

Remarks
Time O(1) amortized, Space O(1)
- Defined in data-structures/heap/heap.ts:336

addMany

addMany(elements): boolean[]
Insert many elements from an iterable.
Parameters
- elements: Iterable<E | R, any, any>
  Iterable of elements or raw values.
Returns boolean[]
Array of per-element success flags.

Remarks
Time O(N log N), Space O(1)
- Defined in data-structures/heap/heap.ts:348

clear

clear(): void
Remove all elements.

Returns void
void

Remarks
Time O(1), Space O(1)
Overrides IterableElementBase.clear
- Defined in data-structures/heap/heap.ts:405

clone

clone(): this
Deep clone this heap.

Returns this
A new heap with the same elements.

Remarks
Time O(N), Space O(N)
Overrides IterableElementBase.clone
- Defined in data-structures/heap/heap.ts:570

delete

delete(element): boolean
Delete one occurrence of an element.
Parameters
- element: E
  Element to delete.
Returns boolean
True if an element was removed.

Remarks
Time O(N), Space O(1)
- Defined in data-structures/heap/heap.ts:440

deleteBy

deleteBy(predicate): boolean
Delete the first element that matches a predicate.
Parameters
- predicate: ((element: E, index: number, heap: this) => boolean)
  Function (element, index, heap) → boolean.
  - - (element, index, heap): boolean
    - Parameters
      element: E
      index: number
      heap: this
      Returns boolean
Returns boolean
True if an element was removed.

Remarks
Time O(N), Space O(1)
- Defined in data-structures/heap/heap.ts:468

dfs

dfs(order?): E[]
Traverse the binary heap as a complete binary tree and collect elements.
Parameters
- Optionalorder: DFSOrderPattern = 'PRE'
  Traversal order: 'PRE' | 'IN' | 'POST'.
Returns E[]
Array of visited elements.

Remarks
Time O(N), Space O(H)
- Defined in data-structures/heap/heap.ts:508

every

every(predicate, thisArg?): boolean
Tests whether all elements satisfy the predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Function invoked for each element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns boolean
true if every element passes; otherwise false.

Remarks
Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).
Inherited from IterableElementBase.every
- Defined in data-structures/base/iterable-element-base.ts:86

filter

filter(callback, thisArg?): this
Filter elements into a new heap of the same class.
Parameters
- callback: ElementCallback<E, R, boolean>
  Predicate (element, index, heap) → boolean to keep element.
- OptionalthisArg: unknown
  Value for this inside the callback.
Returns this
A new heap with the kept elements.

Remarks
Time O(N log N), Space O(N)
Overrides IterableElementBase.filter
- Defined in data-structures/heap/heap.ts:584

find

find<S>(predicate, thisArg?): undefined | S
Finds the first element that satisfies the predicate and returns it.

Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.
Type Parameters
- S
Parameters
- predicate: ElementCallback<E, R, S>
  Type-guard predicate: (value, index, self) => value is S.
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns undefined | S
The matched element typed as S, or undefined if not found.

Remarks
Time O(n) in the worst case; may exit early on the first match. Space O(1).
Inherited from IterableElementBase.find
- Defined in data-structures/base/iterable-element-base.ts:162

fix

fix(): boolean[]
Restore heap order bottom-up (heapify in-place).

Returns boolean[]
Array of per-node results from fixing steps.

Remarks
Time O(N), Space O(1)
- Defined in data-structures/heap/heap.ts:539

forEach

forEach(callbackfn, thisArg?): void
Invokes a callback for each element in iteration order.
Parameters
- callbackfn: ElementCallback<E, R, void>
  Function invoked per element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the callback.
Returns void
void.

Remarks
Time O(n), Space O(1).
Inherited from IterableElementBase.forEach
- Defined in data-structures/base/iterable-element-base.ts:132

has

has(element): boolean
Check if an equal element exists in the heap.
Parameters
- element: E
  Element to search for.
Returns boolean
True if found.

Remarks
Time O(N), Space O(1)
Overrides IterableElementBase.has
- Defined in data-structures/heap/heap.ts:428

isEmpty

isEmpty(): boolean
Check whether the heap is empty.

Returns boolean
True if size is 0.

Remarks
Time O(1), Space O(1)
Overrides IterableElementBase.isEmpty
- Defined in data-structures/heap/heap.ts:395

map

map<EM, RM>(callback, options, thisArg?): Heap<EM, RM>
Map elements into a new heap of possibly different element type.
Type Parameters
- EM
- RM
Parameters
- callback: ElementCallback<E, R, EM>
  Mapping function (element, index, heap) → newElement.
- options: IterableElementBaseOptions<EM, RM> & {
  comparator?: Comparator<EM>;
  } & {
  comparator: Comparator<EM>;
  }
  Options for the output heap, including comparator for EM.
- OptionalthisArg: unknown
  Value for this inside the callback.
Returns Heap<EM, RM>
A new heap with mapped elements.

Remarks
Time O(N log N), Space O(N)
Overrides IterableElementBase.map
- Defined in data-structures/heap/heap.ts:608

mapSame

mapSame(callback, thisArg?): this
Map elements into a new heap of the same element type.
Parameters
- callback: ElementCallback<E, R, E>
  Mapping function (element, index, heap) → element.
- OptionalthisArg: unknown
  Value for this inside the callback.
Returns this
A new heap with mapped elements.

Remarks
Time O(N log N), Space O(N)
Overrides IterableElementBase.mapSame
- Defined in data-structures/heap/heap.ts:632

peek

peek(): undefined | E
Get the current top element without removing it.

Returns undefined | E
Top element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/heap/heap.ts:385

poll

poll(): undefined | E
Remove and return the top element.

Returns undefined | E
Top element or undefined.

Remarks
Time O(log N), Space O(1)
- Defined in data-structures/heap/heap.ts:368

print

print(): void
Prints toVisual() to the console. Intended for quick debugging.

Returns void
void.

Remarks
Time O(n) due to materialization, Space O(n) for the intermediate representation.
Inherited from IterableElementBase.print
- Defined in data-structures/base/iterable-element-base.ts:268

reduce

reduce(callbackfn): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
Returns E
Inherited from IterableElementBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:193
reduce(callbackfn, initialValue): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
- initialValue: E
Returns E
Inherited from IterableElementBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:194
reduce<U>(callbackfn, initialValue): U
Type Parameters
- U
Parameters
- callbackfn: ReduceElementCallback<E, R, U>
- initialValue: U
Returns U
Inherited from IterableElementBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:195

refill

refill(elements): boolean[]
Replace the backing array and rebuild the heap.
Parameters
- elements: Iterable<E, any, any>
  Iterable used to refill the heap.
Returns boolean[]
Array of per-node results from fixing steps.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/heap/heap.ts:416

setEquality

setEquality(equals): this
Set the equality comparator used by has/delete operations.
Parameters
- equals: ((a: E, b: E) => boolean)
  Equality predicate (a, b) → boolean.
  - - (a, b): boolean
    - Parameters
      a: E
      b: E
      Returns boolean
Returns this
This heap.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/heap/heap.ts:496

some

some(predicate, thisArg?): boolean
Tests whether at least one element satisfies the predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Function invoked for each element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns boolean
true if any element passes; otherwise false.

Remarks
Time O(n) in the worst case; may exit early on first success. Space O(1).
Inherited from IterableElementBase.some
- Defined in data-structures/base/iterable-element-base.ts:109

sort

sort(): E[]
Return all elements in ascending order by repeatedly polling.

Returns E[]
Sorted array of elements.

Remarks
Time O(N log N), Space O(N)
- Defined in data-structures/heap/heap.ts:553

toArray

toArray(): E[]
Materializes the elements into a new array.

Returns E[]
A shallow array copy of the iteration order.

Remarks
Time O(n), Space O(n).
Inherited from IterableElementBase.toArray
- Defined in data-structures/base/iterable-element-base.ts:245

toVisual

toVisual(): E[]
Returns a representation of the structure suitable for quick visualization. Defaults to an array of elements; subclasses may override to provide richer visuals.

Returns E[]
A visual representation (array by default).

Remarks
Time O(n), Space O(n).
Inherited from IterableElementBase.toVisual
- Defined in data-structures/base/iterable-element-base.ts:257

values

values(): IterableIterator<E, any, any>
Returns an iterator over the values (alias of the default iterator).

Returns IterableIterator<E, any, any>
An IterableIterator<E> over all elements.

Remarks
Creating the iterator is O(1); full iteration is Time O(n), Space O(1).
Inherited from IterableElementBase.values
- Defined in data-structures/base/iterable-element-base.ts:71

`Static`from

from<T, R, S>(this, elements?, options?): S
Create a heap of the same class from an iterable.
Type Parameters
- T
- R = any
- S extends Heap<T, R> = Heap<T, R>
Parameters
- this: Object
- Optionalelements: Iterable<T | R, any, any>
  Iterable of elements or raw records.
- Optionaloptions: HeapOptions<T, R>
  Heap options including comparator.
Returns S
A new heap instance of this class.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/heap/heap.ts:307

`Static`heapify

heapify<EE, RR>(elements, options): Heap<EE, RR>
Build a Heap from an iterable in linear time given a comparator.
Type Parameters
- EE = any
- RR = any
Parameters
- elements: Iterable<EE, any, any>
  Iterable of elements.
- options: HeapOptions<EE, RR>
  Heap options including comparator.
Returns Heap<EE, RR>
A new Heap built from elements.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/heap/heap.ts:325

Class Heap<E, R>

Remarks

Example

Example

Example

Example

Example

Example

Example

Type Parameters

Hierarchy (view full)

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns Heap<E, R>

Remarks

Properties

Protected Optional_toElementFn

Remarks

Accessors

comparator

Returns Comparator<E>

Remarks

elements

Returns E[]

Remarks

leaf

Returns undefined | E

Remarks

size

Returns number

Remarks

toElementFn

Returns undefined | ((rawElement: R) => E)

Remarks

Methods

Protected_createInstance

Parameters

Returns this

Remarks

Protected_createLike

Type Parameters

Parameters

Returns Heap<EM, RM>

Remarks

Protected_getIterator

Returns IterableIterator<E, any, any>

Remarks

Protected_spawnLike

Type Parameters

Parameters

Returns Heap<EM, RM>

Remarks

[iterator]

Parameters

Returns IterableIterator<E, any, any>

Remarks

add

Parameters

Returns boolean

Remarks

addMany

Parameters

Returns boolean[]

Remarks

clear

Returns void

Remarks

clone

Returns this

Remarks

delete

Parameters

Returns boolean

`Protected` `Optional`_toElementFn

`Protected`_createInstance

`Protected`_createLike

`Protected`_getIterator

`Protected`_spawnLike