Class Heap<T>

Heap

Type Parameters

Hierarchy

Heap

Implements

Iterable<T>

Constructors

constructor

new Heap<T>(compare?): Heap<T>
Heap instance constructor.
Type Parameters
- T
Parameters
- compare: Comparator<T> = Heap.minComparator
  
  Optional comparison function, defaults to Heap.minComparator
Returns Heap<T>
- Defined in Heap.ts:44

Properties

_limit

_limit: number = 0

compare

compare: Comparator<T> = Heap.minComparator

Optional comparison function, defaults to Heap.minComparator

element

element: (() => undefined | T) = ...

Type declaration

- (): undefined | T
- Alias of __type
  
  Returns undefined | T
  
  See
  peek

heapArray

heapArray: T[] = []

offer

offer: ((element) => boolean) = ...

Type declaration

- (element): boolean
- Alias of __type
  Parameters
  - element: T
  Returns boolean
  
  See
  add

poll

poll: (() => undefined | T) = ...

Type declaration

- (): undefined | T
- Alias of __type
  
  Returns undefined | T
  
  See
  pop

removeAll

removeAll: (() => void) = ...

Type declaration

- (): void
- Alias of __type
  
  Returns void
  
  See
  clear

Accessors

length

get length(): number
Length of the heap. Aliases: size.

Returns number

See
size
- Defined in Heap.ts:512

limit

get limit(): number
Get length limit of the heap. Use setLimit or limit to set the limit.

Returns number

See
setLimit
- Defined in Heap.ts:522
set limit(_l): void
Set length limit of the heap. Same as using setLimit.
Parameters
- _l: number
  
  Limit, defaults to 0 (no limit). Negative, Infinity, or NaN values set the limit to 0.
Returns void

Description
If the heap is longer than the limit, the needed amount of leafs are removed.

See
setLimit
- Defined in Heap.ts:532

Methods

[iterator]

[iterator](): Iterator<T, any, undefined>
Iterator interface

Returns Iterator<T, any, undefined>
Implementation of Iterable.[iterator]
- Defined in Heap.ts:731

_applyLimit

_applyLimit(): void
Limit heap size if needed

Returns void
- Defined in Heap.ts:747

_bottomN_push

_bottomN_push(n): T[]
Return the bottom (lowest value) N elements of the heap, without corner cases, unsorted
Parameters
- n: number
  
  Number of elements.
Returns T[]
Array of length <= N.
- Defined in Heap.ts:764

_invertedCompare

_invertedCompare(a, b): number
Returns the inverse to the comparison function.
Parameters
- a: T
- b: T
Returns number
- Defined in Heap.ts:793

_moveNode

_moveNode(j, k): void
Move a node to a new index, switching places
Parameters
- j: number
  
  First node index
- k: number
  
  Another node index
Returns void
- Defined in Heap.ts:802

_sortNodeDown

_sortNodeDown(i): void
Move a node down the tree (to the leaves) to find a place where the heap is sorted.
Parameters
- i: number
  
  Index of the node
Returns void
- Defined in Heap.ts:810

_sortNodeUp

_sortNodeUp(i): void
Move a node up the tree (to the root) to find a place where the heap is sorted.
Parameters
- i: number
  
  Index of the node
Returns void
- Defined in Heap.ts:838

_topIdxOf

_topIdxOf(list): number
Return index of the top element
Parameters
- list: T[]
Returns number
- Defined in Heap.ts:933

_topN_fill

_topN_fill(n): T[]
Return the top (highest value) N elements of the heap, without corner cases, unsorted Implementation: init + push.
Parameters
- n: number
  
  Number of elements.
Returns T[]
Array of length <= N.
- Defined in Heap.ts:886

_topN_heap

_topN_heap(n): T[]
Return the top (highest value) N elements of the heap, without corner cases, unsorted Implementation: heap.
Parameters
- n: number
  
  Number of elements.
Returns T[]
Array of length <= N.
- Defined in Heap.ts:920

_topN_push

_topN_push(n): T[]
Return the top (highest value) N elements of the heap, without corner cases, unsorted Implementation: push.
Parameters
- n: number
  
  Number of elements.
Returns T[]
Array of length <= N.
- Defined in Heap.ts:858

_topOf

_topOf(...list): undefined | T
Return the top element
Parameters
- Rest ...list: T[]
Returns undefined | T
- Defined in Heap.ts:953

add

add(element): boolean
Adds an element to the heap. Aliases: offer. Same as: push(element).
Parameters
- element: T
  
  Element to be added
Returns boolean
true
- Defined in Heap.ts:330

addAll

addAll(elements): boolean
Adds an array of elements to the heap. Similar as: push(element, element, ...).
Parameters
- elements: T[]
  
  Elements to be added
Returns boolean
true
- Defined in Heap.ts:342

bottom

bottom(n?): T[]
Return the bottom (lowest value) N elements of the heap.
Parameters
- n: number = 1
  
  Number of elements.
Returns T[]
Array of length <= N.
- Defined in Heap.ts:358

check

check(): undefined | T
Check if the heap is sorted, useful for testing purposes.

Returns undefined | T
Returns an element if something wrong is found, otherwise it's undefined
- Defined in Heap.ts:378

clear

clear(): void
Remove all of the elements from this heap.

Returns void
- Defined in Heap.ts:387

clone

clone(): Heap<T>
Clone this heap

Returns Heap<T>
- Defined in Heap.ts:395

comparator

comparator(): Comparator<T>
Returns the comparison function.

Returns Comparator<T>
- Defined in Heap.ts:406

contains

contains(o, callbackFn?): boolean
Returns true if this queue contains the specified element.
Parameters
- o: T
  
  Element to be found
- callbackFn: IsEqual<T> = Heap.defaultIsEqual
  
  Optional comparison function, receives (element, needle)
Returns boolean
- Defined in Heap.ts:416

get

get(i): T
Get the element at the given index.
Parameters
- i: number
  
  Index to get
Returns T
Element at that index
- Defined in Heap.ts:703

getChildrenOf

getChildrenOf(idx): T[]
Get the elements of these node's children
Parameters
- idx: number
  
  Node index
Returns T[]
Children elements
- Defined in Heap.ts:712

getParentOf

getParentOf(idx): undefined | T
Get the element of this node's parent
Parameters
- idx: number
  
  Node index
Returns undefined | T
Parent element
- Defined in Heap.ts:723

indexOf

indexOf(element, callbackFn?): number
Get the index of the first occurrence of the element in the heap (using the comparator).
Parameters
- element: T
  
  Element to be found
- callbackFn: IsEqual<T> = Heap.defaultIsEqual
  
  Optional comparison function, receives (element, needle)
Returns number
Index or -1 if not found
- Defined in Heap.ts:448

indexOfEvery

indexOfEvery(element, callbackFn?): number[]
Get the indexes of the every occurrence of the element in the heap (using the comparator).
Parameters
- element: T
  
  Element to be found
- callbackFn: IsEqual<T> = Heap.defaultIsEqual
  
  Optional comparison function, receives (element, needle)
Returns number[]
Array of indexes or empty array if not found
- Defined in Heap.ts:472

init

init(array?): void
Initialize a heap, sorting nodes
Parameters
- Optional array: T[]
  
  Optional initial state array
Returns void
- Defined in Heap.ts:424

isEmpty

isEmpty(): boolean
Test if the heap has no elements.

Returns boolean
True if no elements on the heap
- Defined in Heap.ts:438

iterator

iterator(): Iterable<T>
Returns an iterator. To comply with Java interface.

Returns Iterable<T>
- Defined in Heap.ts:740

leafs

leafs(): T[]
Get the leafs of the tree (no children nodes). See also: getChildrenOf and bottom.

Returns T[]
See
- getChildrenOf
- bottom
- Defined in Heap.ts:499

peek

peek(): undefined | T
Top node. Aliases: element. Same as: top(1)[0].

Returns undefined | T
Top node

See
top
- Defined in Heap.ts:565

pop

pop(): undefined | T
Extract the top node (root). Aliases: poll.

Returns undefined | T
Extracted top node, undefined if empty
- Defined in Heap.ts:573

push

push(...elements): boolean
Pushes element(s) to the heap. See also: __type and addAll.
Parameters
- Rest ...elements: T[]
  
  Elements to insert
Returns boolean
True if elements are present
- Defined in Heap.ts:587

pushpop

pushpop(element): T
Same as push & pop in sequence, but faster
Parameters
- element: T
  
  Element to insert
Returns T
Extracted top node
- Defined in Heap.ts:602

remove

remove(o?, callbackFn?): boolean
Remove the first occurrence of an element from the heap.
Parameters
- Optional o: T
  
  Element to be found
- callbackFn: IsEqual<T> = Heap.defaultIsEqual
  
  Optional equality function, receives (element, needle)
Returns boolean
True if the heap was modified
- Defined in Heap.ts:616

replace

replace(element): T
Pop the current peek value, and add the new item.
Parameters
- element: T
  
  Element to replace peek
Returns T
Old peek
- Defined in Heap.ts:645

setLimit

setLimit(_l): number
Set length limit of the heap. Same as assigning to limit but returns NaN if the value was invalid.
Parameters
- _l: number
  
  Limit. Negative, Infinity, or NaN values set the limit to 0.
Returns number
The limit or NaN if the value was negative, or NaN.

See
limit
- Defined in Heap.ts:550

size

size(): number
Size of the heap

Returns number
- Defined in Heap.ts:656

toArray

toArray(): T[]
Clone the heap's internal array

Returns T[]
- Defined in Heap.ts:686

toString

toString(): string
String output, call to Array.prototype.toString()

Returns string
- Defined in Heap.ts:694

top

top(n?): T[]
Return the top (highest value) N elements of the heap.
Parameters
- n: number = 1
  
  Number of elements.
Returns T[]
Array of length <= N.
- Defined in Heap.ts:666

`Static` defaultIsEqual

defaultIsEqual<N>(a, b): boolean
Default equality function.
Type Parameters
- N
Parameters
- a: N
  
  First element
- b: N
  
  Second element
Returns boolean
True if equal, false otherwise
- Defined in Heap.ts:143

`Static` getChildrenIndexOf

getChildrenIndexOf(idx): number[]
Gets children indices for given index.
Parameters
- idx: number
  
  Parent index
Returns number[]
Array of children indices
- Defined in Heap.ts:55

`Static` getParentIndexOf

getParentIndexOf(idx): number
Gets parent index for given index.
Parameters
- idx: number
  
  Children index
Returns number
Parent index, -1 if idx is 0
- Defined in Heap.ts:64

`Static` getSiblingIndexOf

getSiblingIndexOf(idx): number
Gets sibling index for given index.
Parameters
- idx: number
  
  Children index
Returns number
Sibling index, -1 if idx is 0
- Defined in Heap.ts:77

`Static` heapbottom

heapbottom<N>(heapArr, n?, compare?): N[]
Return the n least valuable elements of a heap-like Array
Type Parameters
- N
Parameters
- heapArr: N[]
  
  Array, should be an array-heap
- n: number = 1
  
  Max number of elements
- Optional compare: Comparator<N>
  
  Optional compare function
Returns N[]
Elements
- Defined in Heap.ts:286

`Static` heapify

heapify<N>(arr, compare?): Heap<N>
Converts an array into an array-heap, in place
Type Parameters
- N
Parameters
- arr: N[]
  
  Array to be modified
- Optional compare: Comparator<N>
  
  Optional compare function
Returns Heap<N>
For convenience, it returns a Heap instance
- Defined in Heap.ts:213

`Static` heappop

heappop<N>(heapArr, compare?): undefined | N
Extract the peek of an array-heap
Type Parameters
- N
Parameters
- heapArr: N[]
  
  Array to be modified, should be a heap
- Optional compare: Comparator<N>
  
  Optional compare function
Returns undefined | N
Returns the extracted peek
- Defined in Heap.ts:225

`Static` heappush

heappush<N>(heapArr, item, compare?): void
Pushes a item into an array-heap
Type Parameters
- N
Parameters
- heapArr: N[]
  
  Array to be modified, should be a heap
- item: N
  
  Item to push
- Optional compare: Comparator<N>
  
  Optional compare function
Returns void
- Defined in Heap.ts:236

`Static` heappushpop

heappushpop<N>(heapArr, item, compare?): N
Push followed by pop, faster
Type Parameters
- N
Parameters
- heapArr: N[]
  
  Array to be modified, should be a heap
- item: N
  
  Item to push
- Optional compare: Comparator<N>
  
  Optional compare function
Returns N
Returns the extracted peek
- Defined in Heap.ts:248

`Static` heapreplace

heapreplace<N>(heapArr, item, compare?): N
Replace peek with item
Type Parameters
- N
Parameters
- heapArr: N[]
  
  Array to be modified, should be a heap
- item: N
  
  Item as replacement
- Optional compare: Comparator<N>
  
  Optional compare function
Returns N
Returns the extracted peek
- Defined in Heap.ts:260

`Static` heaptop

heaptop<N>(heapArr, n?, compare?): N[]
Return the n most valuable elements of a heap-like Array
Type Parameters
- N
Parameters
- heapArr: N[]
  
  Array, should be an array-heap
- n: number = 1
  
  Max number of elements
- Optional compare: Comparator<N>
  
  Optional compare function
Returns N[]
Elements
- Defined in Heap.ts:273

`Static` maxComparator

maxComparator<N>(a, b): number
Max heap comparison function.
Type Parameters
- N
Parameters
- a: N
  
  First element
- b: N
  
  Second element
Returns number
0 if they're equal, positive if a goes up, negative if b goes up
- Defined in Heap.ts:107

`Static` maxComparatorNumber

maxComparatorNumber(a, b): number
Max number heap comparison function.
Parameters
- a: number
  
  First element
- b: number
  
  Second element
Returns number
0 if they're equal, positive if a goes up, negative if b goes up
- Defined in Heap.ts:133

`Static` minComparator

minComparator<N>(a, b): number
Min heap comparison function, default.
Type Parameters
- N
Parameters
- a: N
  
  First element
- b: N
  
  Second element
Returns number
0 if they're equal, positive if a goes up, negative if b goes up
- Defined in Heap.ts:91

`Static` minComparatorNumber

minComparatorNumber(a, b): number
Min number heap comparison function, default.
Parameters
- a: number
  
  First element
- b: number
  
  Second element
Returns number
0 if they're equal, positive if a goes up, negative if b goes up
- Defined in Heap.ts:123

`Static` nlargest

nlargest<N>(n, iterable, compare?): N[]
Return the n most valuable elements of an iterable
Type Parameters
- N
Parameters
- n: number
  
  Max number of elements
- iterable: Iterable<N>
- Optional compare: Comparator<N>
  
  Optional compare function
Returns N[]
Elements
- Defined in Heap.ts:299

`Static` nsmallest

nsmallest<N>(n, iterable, compare?): N[]
Return the n least valuable elements of an iterable
Type Parameters
- N
Parameters
- n: number
  
  Max number of elements
- iterable: Iterable<N>
- Optional compare: Comparator<N>
  
  Optional compare function
Returns N[]
Elements
- Defined in Heap.ts:313

`Static` print

print<N>(heap): string
Prints a heap.
Type Parameters
- N
Parameters
- heap: Heap<N>
  
  Heap to be printed
Returns string
- Defined in Heap.ts:152

Class Heap<T>

Type Parameters

T

Hierarchy

Implements

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

T

Parameters

compare: Comparator<T> = Heap.minComparator

Returns Heap<T>

Properties

_limit

compare

element

Type declaration

Returns undefined | T

See

heapArray

offer

Type declaration

Parameters

element: T

Returns boolean

See

poll

Type declaration

Returns undefined | T

See

removeAll

Type declaration

Returns void

See

Accessors

length

Returns number

See

limit

Returns number

See

Parameters

_l: number

Returns void

Description

See

Methods

[iterator]

Returns Iterator<T, any, undefined>

_applyLimit

Returns void

_bottomN_push

Parameters

n: number

Returns T[]

_invertedCompare

Parameters

a: T

b: T

Returns number

_moveNode

Parameters

j: number

k: number

Returns void

_sortNodeDown

Parameters

i: number

Returns void

_sortNodeUp

Parameters

i: number

Returns void

_topIdxOf

Parameters

`Rest` ...list: T[]

`Optional` array: T[]