Class BinaryHeap<T>

A priority queue implemented with a binary heap. The heap is in descending order by default, using JavaScript's built-in comparison operators to sort the values.

Method Average Case Worst Case
peek() O(1) O(1)
pop() O(log n) O(log n)
push(value) O(1) O(log n)

Example: Usage

import {
  ascend,
  BinaryHeap,
  descend,
} from "@std/data-structures";
import { assertEquals } from "@std/assert";

const maxHeap = new BinaryHeap<number>();
maxHeap.push(4, 1, 3, 5, 2);
assertEquals(maxHeap.peek(), 5);
assertEquals(maxHeap.pop(), 5);
assertEquals([...maxHeap], [4, 3, 2, 1]);
assertEquals([...maxHeap], []);

const minHeap = new BinaryHeap<number>(ascend);
minHeap.push(4, 1, 3, 5, 2);
assertEquals(minHeap.peek(), 1);
assertEquals(minHeap.pop(), 1);
assertEquals([...minHeap], [2, 3, 4, 5]);
assertEquals([...minHeap], []);

const words = new BinaryHeap<string>((a, b) => descend(a.length, b.length));
words.push("truck", "car", "helicopter", "tank");
assertEquals(words.peek(), "helicopter");
assertEquals(words.pop(), "helicopter");
assertEquals([...words], ["truck", "tank", "car"]);
assertEquals([...words], []);

Typeparam

T The type of the values stored in the binary heap.

Type Parameters

  • T
Implements
  • Iterable<T>

Constructors

constructor

Accessors

length

Methods

[iterator] clear drain isEmpty peek pop push toArray from

Constructors

constructor

  • new BinaryHeap<T>(compare?): BinaryHeap<T>

  • Construct an empty binary heap.

    Type Parameters

    • T

    Parameters

    • compare: ((a: T, b: T) => number) = descend

      A custom comparison function to sort the values in the heap. By default, the values are sorted in descending order.

        • (a, b): number

        • Parameters

          Returns number

    Returns BinaryHeap<T>

Accessors

length

  • get length(): number

  • The count of values stored in the binary heap.

    The complexity of this operation is O(1).

    Returns number

    The count of values stored in the binary heap.

    Example: Getting the length of the binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = BinaryHeap.from([4, 1, 3, 5, 2]);

    assertEquals(heap.length, 5);

Methods

[iterator]

  • [iterator](): IterableIterator<T, any, any>

  • Create an iterator that retrieves values from the binary heap in order from greatest to least. The binary heap is drained in the process.

    Returns IterableIterator<T, any, any>

    An iterator for retrieving and removing values from the binary heap.

    Example: Getting an iterator for the binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = BinaryHeap.from([4, 1, 3, 5, 2]);

    assertEquals([...heap], [ 5, 4, 3, 2, 1 ]);
    assertEquals([...heap], []);

clear

  • clear(): void

  • Remove all values from the binary heap.

    Returns void

    Example: Clearing the binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = BinaryHeap.from([4, 1, 3, 5, 2]);
    heap.clear();

    assertEquals([...heap], []);

drain

  • drain(): IterableIterator<T, any, any>

  • Create an iterator that retrieves values from the binary heap in order from greatest to least. The binary heap is drained in the process.

    To avoid draining the binary heap, create a copy using BinaryHeap.from and then call BinaryHeap.prototype.drain on the copy.

    Returns IterableIterator<T, any, any>

    An iterator for retrieving and removing values from the binary heap.

    Example: Draining the binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = BinaryHeap.from([4, 1, 3, 5, 2]);

    assertEquals([...heap.drain()], [ 5, 4, 3, 2, 1 ]);
    assertEquals([...heap.drain()], []);

isEmpty

  • isEmpty(): boolean

  • Check if the binary heap is empty.

    Returns boolean

    true if the binary heap is empty, otherwise false.

    Example: Checking if the binary heap is empty

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = new BinaryHeap<number>();

    assertEquals(heap.isEmpty(), true);

    heap.push(42);

    assertEquals(heap.isEmpty(), false);

peek

  • peek(): undefined | T

  • Get the greatest value from the binary heap without removing it, or undefined if the heap is empty.

    The complexity of this operation is O(1).

    Returns undefined | T

    The greatest value from the binary heap, or undefined if it is empty.

    Example: Getting the greatest value from the binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = BinaryHeap.from([4, 1, 3, 5, 2]);

    assertEquals(heap.peek(), 5);

    Example: Getting the greatest value from an empty binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = new BinaryHeap<number>();

    assertEquals(heap.peek(), undefined);

pop

  • pop(): undefined | T

  • Remove the greatest value from the binary heap and return it, or return undefined if the heap is empty.

    Returns undefined | T

    The greatest value from the binary heap, or undefined if the heap is empty.

    Example: Removing the greatest value from the binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = BinaryHeap.from([4, 1, 3, 5, 2]);

    assertEquals(heap.pop(), 5);
    assertEquals([...heap], [4, 3, 2, 1]);

    The complexity of this operation is on average and worst case O(log n), where n is the count of values stored in the binary heap.

    Example: Removing the greatest value from an empty binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = new BinaryHeap<number>();

    assertEquals(heap.pop(), undefined);

push

  • push(...values): number

  • Add one or more values to the binary heap, returning the new length of the heap.

    The complexity of this operation is O(1) on average and O(log n) in the worst case, where n is the count of values stored in the binary heap.

    Parameters

    • Rest...values: T[]

      The values to add to the binary heap.

    Returns number

    The new length of the binary heap.

    Example: Adding values to the binary heap

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = BinaryHeap.from([4, 1, 3, 2]);
    heap.push(5);

    assertEquals([...heap], [5, 4, 3, 2, 1]);

toArray

  • toArray(): T[]

  • Returns the underlying cloned array in arbitrary order without sorting.

    Returns T[]

    An array containing the values in the binary heap.

    Example: Getting the underlying array

    import { BinaryHeap } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const heap = BinaryHeap.from([4, 1, 3, 5, 2]);

    assertEquals(heap.toArray(), [ 5, 4, 3, 1, 2 ]);

Staticfrom

  • from<T>(collection, options?): BinaryHeap<T>

  • Creates a new binary heap from an array like, an iterable object, or an existing binary heap.

    A custom comparison function can be provided to sort the values in a specific order. By default, the values are sorted in descending order, unless a BinaryHeap is passed, in which case the comparison function is copied from the input heap.

    Type Parameters

    • T

    Parameters

    • collection: ArrayLike<T> | Iterable<T, any, any> | BinaryHeap<T>

      An array like, an iterable object, or an existing binary heap.

    • Optionaloptions: {
          compare?: ((a: T, b: T) => number);
      }

      An optional options object to customize the comparison function.

      • Optionalcompare?: ((a: T, b: T) => number)
          • (a, b): number

          • Parameters

            Returns number

    Returns BinaryHeap<T>

    A new binary heap containing the values from the passed collection.

    Example: Creating a binary heap from an iterable object

    import { BinaryHeap } from "@std/data-structures";

    const heap = BinaryHeap.from((function*() { yield* [4, 1, 3, 5, 2]; })());

    Example: Creating a binary heap from an existing binary heap

    import { BinaryHeap } from "@std/data-structures";

    const heap = BinaryHeap.from([4, 1, 3, 5, 2]);
    const copy = BinaryHeap.from(heap);

    Typeparam

    T The type of the values stored in the binary heap.

  • from<T, U, V>(collection, options): BinaryHeap<U>

  • Creates a new binary heap from an array like, an iterable object, or an existing binary heap.

    A custom mapping function can be provided to transform the values before inserting them into the heap.

    A custom comparison function can be provided to sort the values in a specific order. By default, the values are sorted in descending order, unless a BinaryHeap is passed, in which case the comparison function is copied from the input heap. The comparison operator is used to sort the values in the heap after mapping the values.

    Type Parameters

    • T
    • U
    • V = undefined

    Parameters

    • collection: ArrayLike<T> | Iterable<T, any, any> | BinaryHeap<T>

      An array like, an iterable object, or an existing binary heap.

    • options: {
          compare?: ((a: U, b: U) => number);
          map: ((value: T, index: number) => U);
          thisArg?: V;
      }

      The options object to customize the mapping and comparison functions. The thisArg property can be used to set the this value when calling the mapping function.

      • Optionalcompare?: ((a: U, b: U) => number)
          • (a, b): number

          • Parameters

            Returns number

      • map: ((value: T, index: number) => U)
          • (value, index): U

          • Parameters

            • value: T
            • index: number

            Returns U

      • OptionalthisArg?: V

    Returns BinaryHeap<U>

    A new binary heap containing the mapped values from the passed collection.

    Typeparam

    T The type of the values in the passed collection.

    Typeparam

    U The type of the values stored in the binary heap.

    Typeparam

    V The type of the this value when calling the mapping function. Defaults to undefined.

Settings

Member Visibility

On This Page

Constructors
Accessors
Methods