Class Heap<T>

Heap

Type Parameters

Implements

Iterable<T>

Constructors

constructor

new Heap<T>(compare?: Comparator<T>): 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 = ...

Alias of peek

Type declaration

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

See

peek

heapArray

heapArray: T[] = []

offer

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

Alias of add

Type declaration

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

See

add

poll

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

Alias of pop

Type declaration

- (): undefined | T
- Extract the top node (root). Aliases: poll.
  
  Returns undefined | T
  Extracted top node, undefined if empty

See

pop

removeAll

removeAll: () => void = ...

Alias of clear

Type declaration

- (): void
- Remove all of the elements from this heap.
  
  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: number): 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

_applyLimit

_applyLimit(): void
Limit heap size if needed

Returns void
- Defined in Heap.ts:751

_bottomN_push

_bottomN_push(n: number): 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:768

_invertedCompare

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

_moveNode

_moveNode(j: number, k: number): 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:806

_sortNodeDown

_sortNodeDown(i: number): 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:814

_sortNodeUp

_sortNodeUp(i: number): 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:836

_topIdxOf

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

_topN_fill

_topN_fill(n: number): 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:881

_topN_heap

_topN_heap(n: number): 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:915

_topN_push

_topN_push(n: number): 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:853

_topOf

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

[iterator]

"[iterator]"(): Iterator<T>
Iterator interface

Returns Iterator<T>
Implementation of Iterable.[iterator]
- Defined in Heap.ts:735

add

add(element: T): 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: T[]): 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?: number): 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: T, callbackFn?: IsEqual<T>): 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: number): T
Get the element at the given index.
Parameters
- i: number
  Index to get
Returns T
Element at that index
- Defined in Heap.ts:707

getChildrenOf

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

getParentOf

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

indexOf

indexOf(element: T, callbackFn?: IsEqual<T>): 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: T, callbackFn?: IsEqual<T>): 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?: T[]): void
Initialize a heap, sorting nodes
Parameters
- Optionalarray: 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:744

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: T[]): boolean
Pushes element(s) to the heap. See also: add and addAll.
Parameters
- ...elements: T[]
  Elements to insert
Returns boolean
True if elements are present
- Defined in Heap.ts:587

pushpop

pushpop(element: T): 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?: T, callbackFn?: IsEqual<T>): boolean
Remove the first occurrence of an element from the heap.
Parameters
- Optionalo: 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): 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:649

setLimit

setLimit(_l: number): 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:660

toArray

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

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

top

top(n?: number): 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:670

toString

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

Returns string
- Defined in Heap.ts:698

`Static`defaultIsEqual

defaultIsEqual<N>(a: N, b: N): 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): 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): 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): 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[], n?: number, compare?: Comparator<N>): 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
- Optionalcompare: Comparator<N>
  Optional compare function
Returns N[]
Elements
- Defined in Heap.ts:286

`Static`heapify

heapify<N>(arr: N[], compare?: Comparator<N>): Heap<N>
Converts an array into an array-heap, in place
Type Parameters
- N
Parameters
- arr: N[]
  Array to be modified
- Optionalcompare: 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: N[], compare?: Comparator<N>): undefined | N
Extract the peek of an array-heap
Type Parameters
- N
Parameters
- heapArr: N[]
  Array to be modified, should be a heap
- Optionalcompare: Comparator<N>
  Optional compare function
Returns undefined | N
Returns the extracted peek
- Defined in Heap.ts:225

`Static`heappush

heappush<N>(heapArr: N[], item: N, compare?: Comparator<N>): 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
- Optionalcompare: Comparator<N>
  Optional compare function
Returns void
- Defined in Heap.ts:236

`Static`heappushpop

heappushpop<N>(heapArr: N[], item: N, compare?: Comparator<N>): 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
- Optionalcompare: Comparator<N>
  Optional compare function
Returns N
Returns the extracted peek
- Defined in Heap.ts:248

`Static`heapreplace

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

`Static`heaptop

heaptop<N>(heapArr: N[], n?: number, compare?: Comparator<N>): 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
- Optionalcompare: Comparator<N>
  Optional compare function
Returns N[]
Elements
- Defined in Heap.ts:273

`Static`maxComparator

maxComparator<N>(a: N, b: N): 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: number, b: number): 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: N, b: N): 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: number, b: number): 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: number, iterable: Iterable<N>, compare?: Comparator<N>): N[]
Return the n most valuable elements of an iterable
Type Parameters
- N
Parameters
- n: number
  Max number of elements
- iterable: Iterable<N>
- Optionalcompare: Comparator<N>
  Optional compare function
Returns N[]
Elements
- Defined in Heap.ts:299

`Static`nsmallest

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

`Static`print

print<N>(heap: Heap<N>): 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

Implements

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns Heap<T>

Properties

_limit

compare

element

Type declaration

Returns undefined | T

See

See

heapArray

offer

Type declaration

Parameters

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

Returns void

Description

See

Methods

_applyLimit

Returns void

_bottomN_push

Parameters

Returns T[]

_invertedCompare

Parameters

Returns number

_moveNode

Parameters

Returns void

_sortNodeDown

Parameters

Returns void

_sortNodeUp

Parameters

Returns void

_topIdxOf

Parameters

Returns number

_topN_fill

Parameters

Returns T[]

_topN_heap

Parameters

Returns T[]

_topN_push

Parameters

Returns T[]

_topOf

Parameters

Returns undefined | T

[iterator]