MinPriorityQueue
data-structure-typed / MinPriorityQueue
Class: MinPriorityQueue<E, R>
Defined in: data-structures/priority-queue/min-priority-queue.ts:74
Min-oriented priority queue (min-heap) built on PriorityQueue. The queue removes the smallest element first under the provided comparator. Provide a custom comparator if you store non-primitive objects.
Examples
// Shortest job first scheduling
const jobs = new MinPriorityQueue<number>();
jobs.add(8); // 8 seconds
jobs.add(2); // 2 seconds
jobs.add(5); // 5 seconds
jobs.add(1); // 1 second
// Shortest job first
console.log(jobs.poll()); // 1;
console.log(jobs.poll()); // 2;
console.log(jobs.poll()); // 5;
console.log(jobs.poll()); // 8;
// Event-driven simulation with timestamps
interface Event {
time: number;
action: string;
}
const timeline = new MinPriorityQueue<Event>([], {
comparator: (a, b) => a.time - b.time
});
timeline.add({ time: 300, action: 'Timeout' });
timeline.add({ time: 100, action: 'Request received' });
timeline.add({ time: 200, action: 'Processing done' });
timeline.add({ time: 150, action: 'Cache hit' });
const order = [];
while (timeline.size > 0) {
order.push(timeline.poll()!.action);
}
console.log(order); // ['Request received', 'Cache hit', 'Processing done', 'Timeout'];
// Huffman coding frequency selection
// Character frequencies for Huffman tree building
const freq = new MinPriorityQueue<[number, string]>([], {
comparator: (a, b) => a[0] - b[0]
});
freq.add([5, 'a']);
freq.add([9, 'b']);
freq.add([12, 'c']);
freq.add([2, 'd']);
// Always pick two lowest frequencies
const first = freq.poll()!;
const second = freq.poll()!;
console.log(first[1]); // 'd'; // freq 2
console.log(second[1]); // 'a'; // freq 5
// Combined node goes back
freq.add([first[0] + second[0], first[1] + second[1]]);
console.log(freq.peek()![0]); // 7;
Extends
PriorityQueue<E,R>
Type Parameters
E
E = any
Element type stored in the queue.
R
R = any
Extra record/metadata associated with each element.
Constructors
Constructor
new MinPriorityQueue<E, R>(elements?, options?): MinPriorityQueue<E, R>;
Defined in: data-structures/priority-queue/min-priority-queue.ts:81
Creates a min-priority queue.
Parameters
elements?
Iterable<E, any, any> | Iterable<R, any, any>
Optional initial elements to insert.
options?
PriorityQueueOptions<E, R>
Optional configuration (e.g., comparator, toElementFn).
Returns
MinPriorityQueue<E, R>
Remarks
Complexity — Time: O(n log n) when inserting n elements incrementally; Space: O(n).
Overrides
PriorityQueue<E, R>.constructor
Properties
comparator
Get Signature
get comparator(): Comparator<E>;
Defined in: data-structures/heap/heap.ts:211
Get the comparator used to order elements.
Remarks
Time O(1), Space O(1)
Returns
Comparator<E>
Comparator function.
Inherited from
elements
Get Signature
get elements(): E[];
Defined in: data-structures/heap/heap.ts:175
Get the backing array of the heap.
Remarks
Time O(1), Space O(1)
Returns
E[]
Internal elements array.
Inherited from
leaf
Get Signature
get leaf(): E | undefined;
Defined in: data-structures/heap/heap.ts:202
Get the last leaf element.
Remarks
Time O(1), Space O(1)
Returns
E | undefined
Last element or undefined.
Inherited from
size
Get Signature
get size(): number;
Defined in: data-structures/heap/heap.ts:193
Get the number of elements.
Remarks
Time O(1), Space O(1)
Example
// Track heap capacity
const heap = new Heap<number>();
console.log(heap.size); // 0;
heap.add(10);
heap.add(20);
console.log(heap.size); // 2;
heap.poll();
console.log(heap.size); // 1;
Returns
number
Heap size.
Inherited from
toElementFn
Get Signature
get toElementFn(): ((rawElement) => E) | undefined;
Defined in: data-structures/base/iterable-element-base.ts:48
Exposes the current toElementFn, if configured.
Remarks
Time O(1), Space O(1).
Returns
((rawElement) => E) | undefined
The converter function or undefined when not set.
Inherited from
Methods
[iterator]()
iterator: IterableIterator<E>;
Defined in: data-structures/base/iterable-element-base.ts:61
Returns an iterator over the structure's elements.
Parameters
args
...unknown[]
Optional iterator arguments forwarded to the internal iterator.
Returns
IterableIterator<E>
An IterableIterator<E> that yields the elements in traversal order.
Remarks
Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.
Inherited from
add()
add(element): boolean;
Defined in: data-structures/heap/heap.ts:273
Insert an element.
Parameters
element
E
Element to insert.
Returns
boolean
True.
Remarks
Time O(log N) amortized, Space O(1)
Example
// basic Heap creation and add operation
// Create a min heap (default)
const minHeap = new Heap([5, 3, 7, 1, 9, 2]);
// Verify size
console.log(minHeap.size); // 6;
// Add new element
minHeap.add(4);
console.log(minHeap.size); // 7;
// Min heap property: smallest element at root
const min = minHeap.peek();
console.log(min); // 1;
Inherited from
addMany()
addMany(elements): boolean[];
Defined in: data-structures/heap/heap.ts:290
Insert many elements from an iterable.
Parameters
elements
Iterable<E | R>
Iterable of elements or raw values.
Returns
boolean[]
Array of per-element success flags.
Remarks
Time O(N log N), Space O(1)
Example
// Add multiple elements
const heap = new Heap<number>([], { comparator: (a, b) => a - b });
heap.addMany([5, 3, 7, 1]);
console.log(heap.peek()); // 1;
console.log(heap.size); // 4;
Inherited from
clear()
clear(): void;
Defined in: data-structures/heap/heap.ts:475
Remove all elements.
Returns
void
void
Remarks
Time O(1), Space O(1)
Example
// Remove all elements
const heap = new Heap<number>([1, 2, 3], { comparator: (a, b) => a - b });
heap.clear();
console.log(heap.isEmpty()); // true;
Inherited from
clone()
clone(): this;
Defined in: data-structures/heap/heap.ts:654
Deep clone this heap.
Returns
this
A new heap with the same elements.
Remarks
Time O(N), Space O(N)
Example
// Create independent copy
const heap = new Heap<number>([3, 1, 4], { comparator: (a, b) => a - b });
const copy = heap.clone();
copy.poll();
console.log(heap.size); // 3;
console.log(copy.size); // 2;
Inherited from
delete()
delete(element): boolean;
Defined in: data-structures/heap/heap.ts:506
Delete one occurrence of an element.
Parameters
element
E
Element to delete.
Returns
boolean
True if an element was removed.
Remarks
Time O(N), Space O(1)
Example
// Remove specific element
const heap = new Heap<number>([3, 1, 4, 1, 5], { comparator: (a, b) => a - b });
heap.delete(4);
console.log(heap.toArray().includes(4)); // false;
Inherited from
deleteBy()
deleteBy(predicate): boolean;
Defined in: data-structures/heap/heap.ts:530
Parameters
predicate
(element, index, heap) => boolean
Returns
boolean
Deprecated
Use deleteWhere instead. Will be removed in a future major version.
Inherited from
deleteWhere()
deleteWhere(predicate): boolean;
Defined in: data-structures/heap/heap.ts:540
Delete the first element that matches a predicate.
Parameters
predicate
(element, index, heap) => boolean
Function (element, index, heap) → boolean.
Returns
boolean
True if an element was removed.
Remarks
Time O(N), Space O(1)
Inherited from
dfs()
dfs(order?): E[];
Defined in: data-structures/heap/heap.ts:583
Traverse the binary heap as a complete binary tree and collect elements.
Parameters
order?
DFSOrderPattern = 'PRE'
Traversal order: 'PRE' | 'IN' | 'POST'.
Returns
E[]
Array of visited elements.
Remarks
Time O(N), Space O(H)
Example
// Depth-first traversal
const heap = new Heap<number>([3, 1, 2], { comparator: (a, b) => a - b });
const result = heap.dfs('IN');
console.log(result.length); // 3;
Inherited from
entries()
entries(): IterableIterator<[number, E]>;
Defined in: data-structures/base/iterable-element-base.ts:207
Return an iterator of [index, value] pairs (Array-compatible).
Returns
IterableIterator<[number, E]>
Remarks
Provided for familiarity when migrating from Array. Time O(n), Space O(1) per step.
Inherited from
every()
every(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-element-base.ts:87
Tests whether all elements satisfy the predicate.
Parameters
predicate
ElementCallback<E, R, boolean>
Function invoked for each element with signature (value, index, self).
thisArg?
unknown
Optional this binding for the predicate.
Returns
boolean
true if every element passes; otherwise false.
Remarks
Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).
Inherited from
filter()
filter(callback, thisArg?): this;
Defined in: data-structures/heap/heap.ts:672
Filter elements into a new heap of the same class.
Parameters
callback
ElementCallback<E, R, boolean>
Predicate (element, index, heap) → boolean to keep element.
thisArg?
unknown
Value for this inside the callback.
Returns
this
A new heap with the kept elements.
Remarks
Time O(N log N), Space O(N)
Example
// Filter elements
const heap = new Heap<number>([1, 2, 3, 4, 5], { comparator: (a, b) => a - b });
const evens = heap.filter(x => x % 2 === 0);
console.log(evens.size); // 2;
Inherited from
find()
Call Signature
find<S>(predicate, thisArg?): S | undefined;
Defined in: data-structures/base/iterable-element-base.ts:163
Finds the first element that satisfies the predicate and returns it.
Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.
Type Parameters
S
S
Parameters
predicate
ElementCallback<E, R, S>
Type-guard predicate: (value, index, self) => value is S.
thisArg?
unknown
Optional this binding for the predicate.
Returns
S | undefined
The matched element typed as S, or undefined if not found.
Remarks
Time O(n) in the worst case; may exit early on the first match. Space O(1).
Inherited from
Call Signature
find(predicate, thisArg?): E | undefined;
Defined in: data-structures/base/iterable-element-base.ts:164
Finds the first element that satisfies the predicate and returns it.
Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.
Parameters
predicate
ElementCallback<E, R, unknown>
Type-guard predicate: (value, index, self) => value is S.
thisArg?
unknown
Optional this binding for the predicate.
Returns
E | undefined
The matched element typed as S, or undefined if not found.
Remarks
Time O(n) in the worst case; may exit early on the first match. Space O(1).
Inherited from
fix()
fix(): boolean[];
Defined in: data-structures/heap/heap.ts:613
Restore heap order bottom-up (heapify in-place).
Returns
boolean[]
Array of per-node results from fixing steps.
Remarks
Time O(N), Space O(1)
Inherited from
forEach()
forEach(callbackfn, thisArg?): void;
Defined in: data-structures/base/iterable-element-base.ts:133
Invokes a callback for each element in iteration order.
Parameters
callbackfn
ElementCallback<E, R, void>
Function invoked per element with signature (value, index, self).
thisArg?
unknown
Optional this binding for the callback.
Returns
void
void.
Remarks
Time O(n), Space O(1).
Inherited from
has()
has(element): boolean;
Defined in: data-structures/heap/heap.ts:490
Check if an equal element exists in the heap.
Parameters
element
E
Element to search for.
Returns
boolean
True if found.
Remarks
Time O(N), Space O(1)
Example
// Check element existence
const heap = new Heap<number>([3, 1, 2], { comparator: (a, b) => a - b });
console.log(heap.has(1)); // true;
console.log(heap.has(99)); // false;
Inherited from
includes()
includes(element): boolean;
Defined in: data-structures/base/iterable-element-base.ts:199
Check whether a value exists (Array-compatible alias for has).
Parameters
element
E
Element to search for (uses ===).
Returns
boolean
true if found.
Remarks
Provided for familiarity when migrating from Array. Time O(n), Space O(1).
Inherited from
isEmpty()
isEmpty(): boolean;
Defined in: data-structures/heap/heap.ts:461
Check whether the heap is empty.
Returns
boolean
True if size is 0.
Remarks
Time O(1), Space O(1)
Example
// Check if heap is empty
const heap = new Heap<number>([], { comparator: (a, b) => a - b });
console.log(heap.isEmpty()); // true;
heap.add(1);
console.log(heap.isEmpty()); // false;
Inherited from
keys()
keys(): IterableIterator<number>;
Defined in: data-structures/base/iterable-element-base.ts:218
Return an iterator of numeric indices (Array-compatible).
Returns
IterableIterator<number>
Remarks
Provided for familiarity when migrating from Array. Time O(n), Space O(1) per step.
Inherited from
map()
map<EM, RM>(
callback,
options,
thisArg?): Heap<EM, RM>;
Defined in: data-structures/heap/heap.ts:700
Map elements into a new heap of possibly different element type.
Type Parameters
EM
EM
RM
RM
Parameters
callback
ElementCallback<E, R, EM>
Mapping function (element, index, heap) → newElement.
options
IterableElementBaseOptions<EM, RM> & object & object
Options for the output heap, including comparator for EM.
thisArg?
unknown
Value for this inside the callback.
Returns
Heap<EM, RM>
A new heap with mapped elements.
Remarks
Time O(N log N), Space O(N)
Example
// Transform elements
const heap = new Heap<number>([1, 2, 3], { comparator: (a, b) => a - b });
const doubled = heap.map(x => x * 2, { comparator: (a, b) => a - b });
console.log(doubled.peek()); // 2;
Inherited from
mapSame()
mapSame(callback, thisArg?): this;
Defined in: data-structures/heap/heap.ts:723
Map elements into a new heap of the same element type.
Parameters
callback
ElementCallback<E, R, E>
Mapping function (element, index, heap) → element.
thisArg?
unknown
Value for this inside the callback.
Returns
this
A new heap with mapped elements.
Remarks
Time O(N log N), Space O(N)
Inherited from
peek()
peek(): E | undefined;
Defined in: data-structures/heap/heap.ts:446
Get the current top element without removing it.
Returns
E | undefined
Top element or undefined.
Remarks
Time O(1), Space O(1)
Example
// Heap for event processing with priority
interface Event {
id: number;
type: 'critical' | 'warning' | 'info';
timestamp: number;
message: string;
}
// Custom priority: critical > warning > info
const priorityMap = { critical: 3, warning: 2, info: 1 };
const eventHeap = new Heap<Event>([], {
comparator: (a: Event, b: Event) => {
const priorityA = priorityMap[a.type];
const priorityB = priorityMap[b.type];
return priorityB - priorityA; // Higher priority first
}
});
// Add events in random order
eventHeap.add({ id: 1, type: 'info', timestamp: 100, message: 'User logged in' });
eventHeap.add({ id: 2, type: 'critical', timestamp: 101, message: 'Server down' });
eventHeap.add({ id: 3, type: 'warning', timestamp: 102, message: 'High memory' });
eventHeap.add({ id: 4, type: 'info', timestamp: 103, message: 'Cache cleared' });
eventHeap.add({ id: 5, type: 'critical', timestamp: 104, message: 'Database error' });
console.log(eventHeap.size); // 5;
// Process events by priority (critical first)
const processedOrder: Event[] = [];
while (eventHeap.size > 0) {
const event = eventHeap.poll();
if (event) {
processedOrder.push(event);
}
}
// Verify critical events came first
console.log(processedOrder[0].type); // 'critical';
console.log(processedOrder[1].type); // 'critical';
console.log(processedOrder[2].type); // 'warning';
console.log(processedOrder[3].type); // 'info';
console.log(processedOrder[4].type); // 'info';
// Verify O(log n) operations
const newHeap = new Heap<number>([5, 3, 7, 1]);
// Add - O(log n)
newHeap.add(2);
console.log(newHeap.size); // 5;
// Poll - O(log n)
const removed = newHeap.poll();
console.log(removed); // 1;
// Peek - O(1)
const top = newHeap.peek();
console.log(top); // 2;
Inherited from
poll()
poll(): E | undefined;
Defined in: data-structures/heap/heap.ts:362
Returns
E | undefined
Deprecated
Use pop instead. Will be removed in a future major version.
Example
// Heap with custom comparator (MaxHeap behavior)
interface Task {
id: number;
priority: number;
name: string;
}
// Custom comparator for max heap behavior (higher priority first)
const tasks: Task[] = [
{ id: 1, priority: 5, name: 'Email' },
{ id: 2, priority: 3, name: 'Chat' },
{ id: 3, priority: 8, name: 'Alert' }
];
const maxHeap = new Heap(tasks, {
comparator: (a: Task, b: Task) => b.priority - a.priority
});
console.log(maxHeap.size); // 3;
// Peek returns highest priority task
const topTask = maxHeap.peek();
console.log(topTask?.priority); // 8;
console.log(topTask?.name); // 'Alert';
Inherited from
pop()
pop(): E | undefined;
Defined in: data-structures/heap/heap.ts:371
Remove and return the top element (min or max depending on comparator).
Returns
E | undefined
The removed top element, or undefined if empty.
Remarks
Time O(log N) amortized, Space O(1)
Inherited from
print()
print(): void;
Defined in: data-structures/base/iterable-element-base.ts:298
Prints toVisual() to the console. Intended for quick debugging.
Returns
void
void.
Remarks
Time O(n) due to materialization, Space O(n) for the intermediate representation.
Inherited from
reduce()
Reduces all elements to a single accumulated value.
Param
Reducer of signature (acc, value, index, self) => nextAcc. The first element is used as the initial accumulator.
Param
Reducer of signature (acc, value, index, self) => nextAcc.
Param
The initial accumulator value of type E.
Template
The accumulator type when it differs from E.
Param
Reducer of signature (acc: U, value, index, self) => U.
Param
The initial accumulator value of type U.
Remarks
Time O(n), Space O(1). Throws if called on an empty structure without initialValue.
Call Signature
reduce(callbackfn): E;
Defined in: data-structures/base/iterable-element-base.ts:225
Parameters
callbackfn
ReduceElementCallback<E, R>
Returns
E
Inherited from
Call Signature
reduce(callbackfn, initialValue): E;
Defined in: data-structures/base/iterable-element-base.ts:226
Parameters
callbackfn
ReduceElementCallback<E, R>
initialValue
E
Returns
E
Inherited from
Call Signature
reduce<U>(callbackfn, initialValue): U;
Defined in: data-structures/base/iterable-element-base.ts:227
Type Parameters
U
U
Parameters
callbackfn
ReduceElementCallback<E, R, U>
initialValue
U
Returns
U
Inherited from
setEquality()
setEquality(equals): this;
Defined in: data-structures/heap/heap.ts:567
Set the equality comparator used by has/delete operations.
Parameters
equals
(a, b) => boolean
Equality predicate (a, b) → boolean.
Returns
this
This heap.
Remarks
Time O(1), Space O(1)
Inherited from
some()
some(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-element-base.ts:110
Tests whether at least one element satisfies the predicate.
Parameters
predicate
ElementCallback<E, R, boolean>
Function invoked for each element with signature (value, index, self).
thisArg?
unknown
Optional this binding for the predicate.
Returns
boolean
true if any element passes; otherwise false.
Remarks
Time O(n) in the worst case; may exit early on first success. Space O(1).
Inherited from
sort()
sort(): E[];
Defined in: data-structures/heap/heap.ts:631
Return all elements in ascending order by repeatedly polling.
Returns
E[]
Sorted array of elements.
Remarks
Time O(N log N), Space O(N)
Example
// Sort elements using heap
const heap = new Heap<number>([5, 1, 3, 2, 4]);
const sorted = heap.sort();
console.log(sorted); // [1, 2, 3, 4, 5];
Inherited from
toArray()
toArray(): E[];
Defined in: data-structures/base/iterable-element-base.ts:275
Materializes the elements into a new array.
Returns
E[]
A shallow array copy of the iteration order.
Remarks
Time O(n), Space O(n).
Inherited from
toVisual()
toVisual(): E[];
Defined in: data-structures/base/iterable-element-base.ts:287
Returns a representation of the structure suitable for quick visualization. Defaults to an array of elements; subclasses may override to provide richer visuals.
Returns
E[]
A visual representation (array by default).
Remarks
Time O(n), Space O(n).
Inherited from
values()
values(): IterableIterator<E>;
Defined in: data-structures/base/iterable-element-base.ts:72
Returns an iterator over the values (alias of the default iterator).
Returns
IterableIterator<E>
An IterableIterator<E> over all elements.
Remarks
Creating the iterator is O(1); full iteration is Time O(n), Space O(1).
Inherited from
from()
static from<T, R, S>(
this,
elements?,
options?): S;
Defined in: data-structures/heap/heap.ts:225
Create a heap of the same class from an iterable.
Type Parameters
T
T
R
R = any
S
S extends Heap<T, R> = Heap<T, R>
Parameters
this
Object
elements?
Iterable<T | R, any, any>
Iterable of elements or raw records.
options?
HeapOptions<T, R>
Heap options including comparator.
Returns
S
A new heap instance of this class.
Remarks
Time O(N log N), Space O(N)
Inherited from
heapify()
static heapify<EE, RR>(elements, options): Heap<EE, RR>;
Defined in: data-structures/heap/heap.ts:242
Build a Heap from an iterable in linear time given a comparator.
Type Parameters
EE
EE = any
RR
RR = any
Parameters
elements
Iterable<EE>
Iterable of elements.
options
HeapOptions<EE, RR>
Heap options including comparator.
Returns
Heap<EE, RR>
A new Heap built from elements.
Remarks
Time O(N), Space O(N)
Inherited from
Protected Members
_toElementFn?
protected optional _toElementFn?: (rawElement) => E;
Defined in: data-structures/base/iterable-element-base.ts:39
The converter used to transform a raw element (R) into a public element (E).
Parameters
rawElement
R
Returns
E
Remarks
Time O(1), Space O(1).
Inherited from
Accessors
_createInstance()
protected _createInstance(options?): this;
Defined in: data-structures/heap/heap.ts:785
(Protected) Create an empty instance of the same concrete class.
Parameters
options?
HeapOptions<E, R>
Options to override comparator or toElementFn.
Returns
this
A like-kind empty heap instance.
Remarks
Time O(1), Space O(1)
Inherited from
_createLike()
protected _createLike<EM, RM>(elements?, options?): Heap<EM, RM>;
Defined in: data-structures/heap/heap.ts:799
(Protected) Create a like-kind instance seeded by elements.
Type Parameters
EM
EM
RM
RM
Parameters
elements?
Iterable<EM, any, any> | Iterable<RM, any, any>
Iterable of elements or raw values to seed.
options?
HeapOptions<EM, RM>
Options forwarded to the constructor.
Returns
Heap<EM, RM>
A like-kind heap instance.
Remarks
Time O(N log N), Space O(N)
Inherited from
_getIterator()
protected _getIterator(): IterableIterator<E>;
Defined in: data-structures/heap/heap.ts:744
Internal iterator factory used by the default iterator.
Returns
IterableIterator<E>
An iterator over elements.
Remarks
Implementations should yield in O(1) per element with O(1) extra space when possible.
Inherited from
_spawnLike()
protected _spawnLike<EM, RM>(options?): Heap<EM, RM>;
Defined in: data-structures/heap/heap.ts:818
(Protected) Spawn an empty like-kind heap instance.
Type Parameters
EM
EM
RM
RM
Parameters
options?
HeapOptions<EM, RM>
Options forwarded to the constructor.
Returns
Heap<EM, RM>
An empty like-kind heap instance.
Remarks
Time O(1), Space O(1)