import { BinaryHeap } from "https://deno.land/std@0.223.0/data_structures/binary_heap.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.223.0/data_structures/mod.ts";
import { assertEquals } from "https://deno.land/std@0.223.0/assert/assert_equals.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
[Symbol.iterator](): IterableIterator<T>