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

// Use Heap to sort an array
    function heapSort(arr: number[]): number[] {
      const heap = new Heap<number>(arr, { comparator: (a, b) => a - b });
      const sorted: number[] = [];
      while (!heap.isEmpty()) {
        sorted.push(heap.poll()!); // Poll minimum element
      }
      return sorted;
    }

    const array = [5, 3, 8, 4, 1, 2];
    console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8]

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 merge sorted sequences
    function mergeSortedSequences(sequences: number[][]): number[] {
      const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], {
        comparator: (a, b) => a.value - b.value // Min heap
      });

      // Initialize heap
      sequences.forEach((seq, seqIndex) => {
        if (seq.length) {
          heap.add({ value: seq[0], seqIndex, itemIndex: 0 });
        }
      });

      const merged: number[] = [];
      while (!heap.isEmpty()) {
        const { value, seqIndex, itemIndex } = heap.poll()!;
        merged.push(value);

        if (itemIndex + 1 < sequences[seqIndex].length) {
          heap.add({
            value: sequences[seqIndex][itemIndex + 1],
            seqIndex,
            itemIndex: itemIndex + 1
          });
        }
      }

      return merged;
    }

    const sequences = [
      [1, 4, 7],
      [2, 5, 8],
      [3, 6, 9]
    ];
    console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

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 = unknown
R = never
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 = unknown
- R = never
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:204

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:613

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:223

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:243

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:233

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:659

`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:675

`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:617

`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:692

[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:287

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:299

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:356

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:521

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:391

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:419

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:459

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:535

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:490

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:379

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:346

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:559

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:583

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:336

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:319

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:367

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:447

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:504

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 = never
- 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:258

`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 = unknown
- RR = never
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:276

Class Heap<E, R>

Remarks

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

Remarks

`Protected` `Optional`_toElementFn

`Protected`_createInstance

`Protected`_createLike

`Protected`_getIterator

`Protected`_spawnLike