BinaryHeap - @std/data-structures

class BinaryHeap

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)

Examples

Example 1

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

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

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

Type Parameters

T

Static Methods

from<T>(collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>): BinaryHeap<T>

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

from<T>(collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>,
options: { compare?: (a: T,
b: T
) => number;  }
): BinaryHeap<T>

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>

Properties

readonly

length: number

The amount of values stored in the binary heap.

Methods

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

clear(): void

Removes all values from the binary heap.

drain(): IterableIterator<T>

Returns an iterator for retrieving and removing values from the binary heap.

isEmpty(): boolean

Checks if the binary heap is empty.

peek(): T | undefined

Returns the greatest value in the binary heap, or undefined if it is empty.

pop(): T | undefined

Removes the greatest value from the binary heap and returns it, or null if it is empty.

push(...values: T[]): number

Adds values to the binary heap.

toArray(): T[]

Returns the underlying cloned array in arbitrary order without sorting

@std/data-structures@0.215.0