import { BinaryHeap } from "https://deno.land/std@0.194.0/collections/mod.ts";
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
Example 1
import {
ascend,
BinaryHeap,
descend,
} from "https://deno.land/std@0.194.0/collections/binary_heap.ts";
import { assertEquals } from "https://deno.land/std@0.194.0/testing/asserts.ts";
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], []);
Methods
clear()
Removes all values from the binary heap.
Returns an iterator for retrieving and removing values from the binary heap.
isEmpty(): boolean
Checks if the binary heap is empty.
Removes the greatest value from the binary heap and returns it, or null if it is empty.
toArray()
Returns the underlying cloned array in arbitrary order without sorting
[Symbol.iterator](): IterableIterator<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>