MaxHeap
data-structure-typed / MaxHeap
Class: MaxHeap<E, R>
Defined in: data-structures/heap/max-heap.ts:73
Examples
// Find the K largest elements
const data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const heap = new MaxHeap(data);
// Extract top 3 elements
const top3 = [];
for (let i = 0; i < 3; i++) {
top3.push(heap.poll());
}
console.log(top3); // [9, 6, 5];
// Priority-based task processing
interface Task {
name: string;
priority: number;
}
const heap = new MaxHeap<Task>([], {
comparator: (a, b) => b.priority - a.priority
});
heap.add({ name: 'Low priority', priority: 1 });
heap.add({ name: 'Critical fix', priority: 10 });
heap.add({ name: 'Medium task', priority: 5 });
// Highest priority first
console.log(heap.poll()?.name); // 'Critical fix';
console.log(heap.poll()?.name); // 'Medium task';
console.log(heap.poll()?.name); // 'Low priority';
// Real-time top score tracking
const scores = new MaxHeap<number>();
// Stream of scores coming in
for (const score of [72, 85, 91, 68, 95, 78, 88]) {
scores.add(score);
}
// Current highest score without removing
console.log(scores.peek()); // 95;
console.log(scores.size); // 7;
// Remove top 2 scores
console.log(scores.poll()); // 95;
console.log(scores.poll()); // 91;
console.log(scores.peek()); // 88;
Extends
Heap<E,R>
Type Parameters
E
E = any
R
R = any
Max-oriented binary heap. Notes and typical use-cases are documented in Heap.
- Complete Binary Tree: Heaps are typically complete binary trees, meaning every level is fully filled except possibly for the last level, which has nodes as far left as possible.
- Heap Properties: The value of each parent node is greater than or equal to the value of its children.
- Root Node Access: In a heap, the largest element (in a max heap) or the smallest element (in a min heap) is always at the root of the tree.
- Efficient Insertion and Deletion: Due to its structure, a heap allows for insertion and deletion operations in logarithmic time (O(log n)).
- Managing Dynamic Data Sets: Heaps effectively manage dynamic data sets, especially when frequent access to the largest or smallest elements is required.
- Non-linear Search: While a heap allows rapid access to its largest or smallest element, it is less efficient for other operations, such as searching for a specific element, as it is not designed for these tasks.
- Efficient Sorting Algorithms: For example, heap sort. Heap sort uses the properties of a heap to sort elements.
- Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prim's minimum-spanning tree algorithm, which use heaps to improve performance.
Constructors
Constructor
new MaxHeap<E, R>(elements?, options?): MaxHeap<E, R>;
Defined in: data-structures/heap/max-heap.ts:79
Create a max-heap. For objects, supply a custom comparator.
Parameters
elements?
Iterable<E, any, any> | Iterable<R, any, any>
Optional initial elements.
options?
HeapOptions<E, R>
Optional configuration.
Returns
MaxHeap<E, R>
Overrides
Properties
comparator
Get Signature
get comparator(): Comparator<E>;
Defined in: data-structures/heap/heap.ts:1170
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:180
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:243
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:233
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:47
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:60
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:336
Insert an element.
Parameters
element
E
Element to insert.
Returns
boolean
True.
Remarks
Time O(1) 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:385
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:669
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:1008
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:770
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:798
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:868
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
every()
every(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-element-base.ts:86
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:1059
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:162
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: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.
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:899
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:132
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:722
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
isEmpty()
isEmpty(): boolean;
Defined in: data-structures/heap/heap.ts:622
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
map()
map<EM, RM>(
callback,
options,
thisArg?): Heap<EM, RM>;
Defined in: data-structures/heap/heap.ts:1119
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:1143
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:574
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:464
Remove and return the top element.
Returns
E | undefined
Top element or undefined.
Remarks
Time O(log N), Space O(1)
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
print()
print(): void;
Defined in: data-structures/base/iterable-element-base.ts:268
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:193
Parameters
callbackfn
ReduceElementCallback<E, R>
Returns
E
Inherited from
Call Signature
reduce(callbackfn, initialValue): E;
Defined in: data-structures/base/iterable-element-base.ts:194
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:195
Type Parameters
U
U
Parameters
callbackfn
ReduceElementCallback<E, R, U>
initialValue
U
Returns
U
Inherited from
refill()
refill(elements): boolean[];
Defined in: data-structures/heap/heap.ts:680
Replace the backing array and rebuild the heap.
Parameters
elements
Iterable<E>
Iterable used to refill the heap.
Returns
boolean[]
Array of per-node results from fixing steps.
Remarks
Time O(N), Space O(N)
Inherited from
setEquality()
setEquality(equals): this;
Defined in: data-structures/heap/heap.ts:826
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:109
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:952
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:245
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:257
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:71
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:258
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), Space O(N)
Inherited from
heapify()
static heapify<EE, RR>(elements, options): Heap<EE, RR>;
Defined in: data-structures/heap/heap.ts:276
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:38
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:1216
(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:1234
(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:1174
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:1254
(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)