BinaryHeap

import { BinaryHeap } from "jsr:@ende/data-structures";

class

class BinaryHeap<T> implements Iterable<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 "@ende/data-structures";
import { assertEquals } from "@ende/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], []);

Constructors

constructor

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

Construct an empty binary heap.

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.

Static methods

from

static from<T>(collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>, options?: { compare?: (a: T, b: T) => number }): 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.

collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>

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

options?: { compare?: (a: T, b: T) => number }

An optional options object to customize the comparison function.

Returns

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

Example: Creating a binary heap from an array like

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

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

Example: Creating a binary heap from an iterable object

import { BinaryHeap } from "@ende/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 "@ende/data-structures";

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

Example: Creating a binary heap from an array like with a custom comparison function

import { BinaryHeap, ascend } from "@ende/data-structures";

const heap = BinaryHeap.from([4, 1, 3, 5, 2], { compare: ascend });
static from<T, U, V = undefined>(collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>, options: { compare?: (a: U, b: U) => number; map: (value: T, index: number) => U; thisArg?: V }): 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.

collection: ArrayLike<T> | Iterable<T> | 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.

Returns

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

Example: Creating a binary heap from an array like with a custom mapping function

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

const heap = BinaryHeap.from([4, 1, 3, 5, 2], { map: (value) => value * 2 });

assertEquals(heap.peek(), 10);
static from<T, U, V>(collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>, options?: { compare?: (a: U, b: U) => number; map?: (value: T, index: number) => U; thisArg?: V }): BinaryHeap<U>

Methods

toArray

toArray(): T[]

Returns the underlying cloned array in arbitrary order without sorting.

Returns

An array containing the values in the binary heap.

Example: Getting the underlying array

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

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

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

length

get length(): number

The count of values stored in the binary heap.

The complexity of this operation is O(1).

Returns

The count of values stored in the binary heap.

Example: Getting the length of the binary heap

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

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

assertEquals(heap.length, 5);

peek

peek(): T | undefined

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

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 "@ende/data-structures";
import { assertEquals } from "@ende/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 "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const heap = new BinaryHeap<number>();

assertEquals(heap.peek(), undefined);

pop

pop(): T | undefined

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

Returns

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 "@ende/data-structures";
import { assertEquals } from "@ende/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 "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const heap = new BinaryHeap<number>();

assertEquals(heap.pop(), undefined);

push

push(...values: T[]): 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.

...values: T[]

The values to add to the binary heap.

Returns

The new length of the binary heap.

Example: Adding values to the binary heap

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

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

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

clear

clear(): void

Remove all values from the binary heap.

Example: Clearing the binary heap

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

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

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

isEmpty

isEmpty(): boolean

Check if the binary heap is empty.

Returns

true if the binary heap is empty, otherwise false.

Example: Checking if the binary heap is empty

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

const heap = new BinaryHeap<number>();

assertEquals(heap.isEmpty(), true);

heap.push(42);

assertEquals(heap.isEmpty(), false);

drain

drain(): IterableIterator<T>

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

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

Example: Draining the binary heap

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

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

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

[Symbol.iterator]

[Symbol.iterator](): IterableIterator<T>

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

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

Example: Getting an iterator for the binary heap

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

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

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

Source