Class MaxHeap<E, R>

Example

Type Parameters

E = any
R = any
Max-oriented binary heap. Notes and typical use-cases are documented in Heap.
1. 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.
2. Heap Properties: The value of each parent node is greater than or equal to the value of its children.
3. 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.
4. Efficient Insertion and Deletion: Due to its structure, a heap allows for insertion and deletion operations in logarithmic time (O(log n)).
5. Managing Dynamic Data Sets: Heaps effectively manage dynamic data sets, especially when frequent access to the largest or smallest elements is required.
6. 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.
7. Efficient Sorting Algorithms: For example, heap sort. Heap sort uses the properties of a heap to sort elements.
8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prim's minimum-spanning tree algorithm, which use heaps to improve performance.

Hierarchy (view full)

Heap<E, R>
- MaxHeap

Index

Constructors

constructor

new MaxHeap<E, R>(elements?, options?): MaxHeap<E, R>
Create a max-heap. For objects, supply a custom comparator.
Type Parameters
- E = any
- R = any
Parameters
- elements: Iterable<E, any, any> | Iterable<R, any, any> = []
  Optional initial elements.
- Optionaloptions: HeapOptions<E, R>
  Optional configuration.
Returns MaxHeap<E, R>
Overrides Heap.constructor
- Defined in data-structures/heap/max-heap.ts:32

Properties

`Protected` `Optional`_toElementFn

_toElementFn?: ((rawElement: R) => E)

The converter used to transform a raw element (R) into a public element (E).

Remarks

Time O(1), Space O(1).

Accessors

comparator

get comparator(): Comparator<E>
Get the comparator used to order elements.

Returns Comparator<E>
Comparator function.

Remarks
Time O(1), Space O(1)
Inherited from Heap.comparator
- Defined in data-structures/heap/heap.ts:613

elements

get elements(): E[]
Get the backing array of the heap.

Returns E[]
Internal elements array.

Remarks
Time O(1), Space O(1)
Inherited from Heap.elements
- Defined in data-structures/heap/heap.ts:223

leaf

get leaf(): undefined | E
Get the last leaf element.

Returns undefined | E
Last element or undefined.

Remarks
Time O(1), Space O(1)
Inherited from Heap.leaf
- Defined in data-structures/heap/heap.ts:243

size

get size(): number
Get the number of elements.

Returns number
Heap size.

Remarks
Time O(1), Space O(1)
Inherited from Heap.size
- Defined in data-structures/heap/heap.ts:233

toElementFn

get toElementFn(): undefined | ((rawElement: R) => E)
Exposes the current toElementFn, if configured.

Returns undefined | ((rawElement: R) => E)
The converter function or undefined when not set.

Remarks
Time O(1), Space O(1).
Inherited from Heap.toElementFn
- Defined in data-structures/base/iterable-element-base.ts:47

Methods

`Protected`_createInstance

_createInstance(options?): this
(Protected) Create an empty instance of the same concrete class.
Parameters
- Optionaloptions: 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 Heap._createInstance
- Defined in data-structures/heap/heap.ts:659

`Protected`_createLike

_createLike<EM, RM>(elements?, options?): Heap<EM, RM>
(Protected) Create a like-kind instance seeded by elements.
Type Parameters
- EM
- RM
Parameters
- Optionalelements: Iterable<EM, any, any> | Iterable<RM, any, any> = []
  Iterable of elements or raw values to seed.
- Optionaloptions: 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 Heap._createLike
- Defined in data-structures/heap/heap.ts:675

`Protected`_getIterator

_getIterator(): IterableIterator<E, any, any>
Internal iterator factory used by the default iterator.

Returns IterableIterator<E, any, any>
An iterator over elements.

Remarks
Implementations should yield in O(1) per element with O(1) extra space when possible.
Inherited from Heap._getIterator
- Defined in data-structures/heap/heap.ts:617

`Protected`_spawnLike

_spawnLike<EM, RM>(options?): Heap<EM, RM>
(Protected) Spawn an empty like-kind heap instance.
Type Parameters
- EM
- RM
Parameters
- Optionaloptions: 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)
Inherited from Heap._spawnLike
- Defined in data-structures/heap/heap.ts:692

[iterator]

[iterator](...args): IterableIterator<E, any, any>
Returns an iterator over the structure's elements.
Parameters
- Rest...args: unknown[]
  Optional iterator arguments forwarded to the internal iterator.
Returns IterableIterator<E, any, any>
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 Heap.[iterator]
- Defined in data-structures/base/iterable-element-base.ts:60

add

add(element): boolean
Insert an element.
Parameters
- element: E
  Element to insert.
Returns boolean
True.

Remarks
Time O(1) amortized, Space O(1)
Inherited from Heap.add
- Defined in data-structures/heap/heap.ts:287

addMany

addMany(elements): boolean[]
Insert many elements from an iterable.
Parameters
- elements: Iterable<E | R, any, any>
  Iterable of elements or raw values.
Returns boolean[]
Array of per-element success flags.

Remarks
Time O(N log N), Space O(1)
Inherited from Heap.addMany
- Defined in data-structures/heap/heap.ts:299

clear

clear(): void
Remove all elements.

Returns void
void

Remarks
Time O(1), Space O(1)
Inherited from Heap.clear
- Defined in data-structures/heap/heap.ts:356

clone

clone(): this
Deep clone this heap.

Returns this
A new heap with the same elements.

Remarks
Time O(N), Space O(N)
Inherited from Heap.clone
- Defined in data-structures/heap/heap.ts:521

delete

delete(element): boolean
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)
Inherited from Heap.delete
- Defined in data-structures/heap/heap.ts:391

deleteBy

deleteBy(predicate): boolean
Delete the first element that matches a predicate.
Parameters
- predicate: ((element: E, index: number, heap: this) => boolean)
  Function (element, index, heap) → boolean.
  - - (element, index, heap): boolean
    - Parameters
      element: E
      index: number
      heap: this
      Returns boolean
Returns boolean
True if an element was removed.

Remarks
Time O(N), Space O(1)
Inherited from Heap.deleteBy
- Defined in data-structures/heap/heap.ts:419

dfs

dfs(order?): E[]
Traverse the binary heap as a complete binary tree and collect elements.
Parameters
- Optionalorder: DFSOrderPattern = 'PRE'
  Traversal order: 'PRE' | 'IN' | 'POST'.
Returns E[]
Array of visited elements.

Remarks
Time O(N), Space O(H)
Inherited from Heap.dfs
- Defined in data-structures/heap/heap.ts:459

every

every(predicate, thisArg?): boolean
Tests whether all elements satisfy the predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Function invoked for each element with signature (value, index, self).
- OptionalthisArg: 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 Heap.every
- Defined in data-structures/base/iterable-element-base.ts:86

filter

filter(callback, thisArg?): this
Filter elements into a new heap of the same class.
Parameters
- callback: ElementCallback<E, R, boolean>
  Predicate (element, index, heap) → boolean to keep element.
- OptionalthisArg: 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)
Inherited from Heap.filter
- Defined in data-structures/heap/heap.ts:535

find

find<S>(predicate, thisArg?): undefined | S
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
Parameters
- predicate: ElementCallback<E, R, S>
  Type-guard predicate: (value, index, self) => value is S.
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns undefined | S
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 Heap.find
- Defined in data-structures/base/iterable-element-base.ts:162

fix

fix(): boolean[]
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 Heap.fix
- Defined in data-structures/heap/heap.ts:490

forEach

forEach(callbackfn, thisArg?): void
Invokes a callback for each element in iteration order.
Parameters
- callbackfn: ElementCallback<E, R, void>
  Function invoked per element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the callback.
Returns void
void.

Remarks
Time O(n), Space O(1).
Inherited from Heap.forEach
- Defined in data-structures/base/iterable-element-base.ts:132

has

has(element): boolean
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)
Inherited from Heap.has
- Defined in data-structures/heap/heap.ts:379

isEmpty

isEmpty(): boolean
Check whether the heap is empty.

Returns boolean
True if size is 0.

Remarks
Time O(1), Space O(1)
Inherited from Heap.isEmpty
- Defined in data-structures/heap/heap.ts:346

map

map<EM, RM>(callback, options, thisArg?): Heap<EM, RM>
Map elements into a new heap of possibly different element type.
Type Parameters
- EM
- RM
Parameters
- callback: ElementCallback<E, R, EM>
  Mapping function (element, index, heap) → newElement.
- options: IterableElementBaseOptions<EM, RM> & {
  comparator?: Comparator<EM>;
  } & {
  comparator: Comparator<EM>;
  }
  Options for the output heap, including comparator for EM.
- OptionalthisArg: 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)
Inherited from Heap.map
- Defined in data-structures/heap/heap.ts:559

mapSame

mapSame(callback, thisArg?): this
Map elements into a new heap of the same element type.
Parameters
- callback: ElementCallback<E, R, E>
  Mapping function (element, index, heap) → element.
- OptionalthisArg: 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 Heap.mapSame
- Defined in data-structures/heap/heap.ts:583

peek

peek(): undefined | E
Get the current top element without removing it.

Returns undefined | E
Top element or undefined.

Remarks
Time O(1), Space O(1)
Inherited from Heap.peek
- Defined in data-structures/heap/heap.ts:336

poll

poll(): undefined | E
Remove and return the top element.

Returns undefined | E
Top element or undefined.

Remarks
Time O(log N), Space O(1)
Inherited from Heap.poll
- Defined in data-structures/heap/heap.ts:319

print

print(): void
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 Heap.print
- Defined in data-structures/base/iterable-element-base.ts:268

reduce

reduce(callbackfn): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
Returns E
Inherited from Heap.reduce
- Defined in data-structures/base/iterable-element-base.ts:193
reduce(callbackfn, initialValue): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
- initialValue: E
Returns E
Inherited from Heap.reduce
- Defined in data-structures/base/iterable-element-base.ts:194
reduce<U>(callbackfn, initialValue): U
Type Parameters
- U
Parameters
- callbackfn: ReduceElementCallback<E, R, U>
- initialValue: U
Returns U
Inherited from Heap.reduce
- Defined in data-structures/base/iterable-element-base.ts:195

refill

refill(elements): boolean[]
Replace the backing array and rebuild the heap.
Parameters
- elements: Iterable<E, any, any>
  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 Heap.refill
- Defined in data-structures/heap/heap.ts:367

setEquality

setEquality(equals): this
Set the equality comparator used by has/delete operations.
Parameters
- equals: ((a: E, b: E) => boolean)
  Equality predicate (a, b) → boolean.
  - - (a, b): boolean
    - Parameters
      a: E
      b: E
      Returns boolean
Returns this
This heap.

Remarks
Time O(1), Space O(1)
Inherited from Heap.setEquality
- Defined in data-structures/heap/heap.ts:447

some

some(predicate, thisArg?): boolean
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).
- OptionalthisArg: 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 Heap.some
- Defined in data-structures/base/iterable-element-base.ts:109

sort

sort(): E[]
Return all elements in ascending order by repeatedly polling.

Returns E[]
Sorted array of elements.

Remarks
Time O(N log N), Space O(N)
Inherited from Heap.sort
- Defined in data-structures/heap/heap.ts:504

toArray

toArray(): E[]
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 Heap.toArray
- Defined in data-structures/base/iterable-element-base.ts:245

toVisual

toVisual(): E[]
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 Heap.toVisual
- Defined in data-structures/base/iterable-element-base.ts:257

values

values(): IterableIterator<E, any, any>
Returns an iterator over the values (alias of the default iterator).

Returns IterableIterator<E, any, any>
An IterableIterator<E> over all elements.

Remarks
Creating the iterator is O(1); full iteration is Time O(n), Space O(1).
Inherited from Heap.values
- Defined in data-structures/base/iterable-element-base.ts:71

`Static`from

from<T, R, S>(this, elements?, options?): S
Create a heap of the same class from an iterable.
Type Parameters
- T
- R = never
- S extends Heap<T, R> = Heap<T, R>
Parameters
- this: Object
- Optionalelements: Iterable<T | R, any, any>
  Iterable of elements or raw records.
- Optionaloptions: 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 Heap.from
- Defined in data-structures/heap/heap.ts:258

`Static`heapify

heapify<EE, RR>(elements, options): Heap<EE, RR>
Build a Heap from an iterable in linear time given a comparator.
Type Parameters
- EE = unknown
- RR = never
Parameters
- elements: Iterable<EE, any, any>
  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 Heap.heapify
- Defined in data-structures/heap/heap.ts:276

Class MaxHeap<E, R>

Example

Type Parameters

Hierarchy (view full)

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns MaxHeap<E, R>

Properties

Protected Optional_toElementFn

Remarks

Accessors

comparator

Returns Comparator<E>

Remarks

elements

Returns E[]

Remarks

leaf

Returns undefined | E

Remarks

size

Returns number

Remarks

toElementFn

Returns undefined | ((rawElement: R) => E)

Remarks

Methods

Protected_createInstance

Parameters

Returns this

Remarks

Protected_createLike

Type Parameters

Parameters

Returns Heap<EM, RM>

Remarks

Protected_getIterator

Returns IterableIterator<E, any, any>

Remarks

Protected_spawnLike

Type Parameters

Parameters

Returns Heap<EM, RM>

Remarks

[iterator]

Parameters

Returns IterableIterator<E, any, any>

Remarks

add

Parameters

Returns boolean

Remarks

addMany

Parameters

Returns boolean[]

Remarks

clear

Returns void

Remarks

clone

Returns this

Remarks

delete

Parameters

Returns boolean

Remarks

deleteBy

Parameters

Parameters

Returns boolean

Returns boolean

Remarks

dfs

`Protected` `Optional`_toElementFn

`Protected`_createInstance

`Protected`_createLike

`Protected`_getIterator

`Protected`_spawnLike