heap-js
Options
All
  • Public
  • Public/Protected
  • All
Menu

Heap

Type parameters

  • T

Hierarchy

  • Heap

Implements

  • Iterable<T>

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

  • Heap instance constructor.

    Parameters

    • Default value compare: Comparator<T> = Heap.minComparator

      Optional comparison function, defaults to Heap.minComparator

    Returns Heap

Properties

_limit

_limit: number = 0

compare

compare: Comparator<T>

Optional comparison function, defaults to Heap.minComparator

element

element: peek = this.peek

Alias of peek

heapArray

heapArray: Array<T> = []

offer

offer: add = this.add

Alias of add

poll

poll: pop = this.pop

Alias of pop

Accessors

length

  • get length(): number

  • Length of the heap.

    Returns number

limit

  • get limit(): number
  • set limit(_l: number): void

  • Get length limit of the heap.

    Returns number

  • Set length limit of the heap.

    Parameters

    • _l: number

    Returns void

Methods

[Symbol.iterator]

  • [Symbol.iterator](): Generator<T, void, unknown>

  • Iterator interface

    Returns Generator<T, void, unknown>

_applyLimit

  • _applyLimit(): void

  • Limit heap size if needed

    Returns void

_bottomN

  • _bottomN(n: number): Array<T>

  • Return the bottom (lowest value) N elements of the heap, without corner cases, unsorted

    Parameters

    • n: number

      Number of elements.

    Returns Array<T>

    Array of length <= N.

_invertedCompare

  • _invertedCompare(a: T, b: T): number

  • Returns the inverse to the comparison function.

    Parameters

    • a: T
    • b: T

    Returns number

_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

_sortNodeDown

  • _sortNodeDown(i: number): boolean

  • 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 boolean

_sortNodeUp

  • _sortNodeUp(i: number): boolean

  • 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 boolean

_topN

  • _topN(n: number): Array<T>

  • Return the top (highest value) N elements of the heap, without corner cases, unsorted

    Parameters

    • n: number

      Number of elements.

    Returns Array<T>

    Array of length <= N.

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

addAll

  • addAll(elements: Array<T>): boolean

  • Adds an array of elements to the heap. Similar as: push(element, element, ...).

    Parameters

    • elements: Array<T>

      Elements to be added

    Returns boolean

    true

bottom

  • bottom(n?: number): Array<T>

  • Return the bottom (lowest value) N elements of the heap.

    Parameters

    • Default value n: number = 1

      Number of elements.

    Returns Array<T>

    Array of length <= N.

check

  • check(): T | undefined

  • Check if the heap is sorted, useful for testing purposes.

    Returns T | undefined

    Returns an element if something wrong is found, otherwise it's undefined

clear

  • clear(): void

  • Remove all of the elements from this heap.

    Returns void

clone

comparator

contains

  • contains(o: T, fn?: IsEqual<T>): boolean

  • Returns true if this queue contains the specified element.

    Parameters

    • o: T

      Element to be found

    • Default value fn: IsEqual<T> = Heap.defaultIsEqual

      Optional comparison function, receives (element, needle)

    Returns boolean

get

  • get(i: number): T

  • Get the element at the given index.

    Parameters

    • i: number

      Index to get

    Returns T

    Element at that index

getChildrenOf

  • getChildrenOf(idx: number): Array<T>

  • Get the elements of these node's children

    Parameters

    • idx: number

      Node index

    Returns Array<T>

    Children elements

getParentOf

  • getParentOf(idx: number): T | undefined

  • Get the element of this node's parent

    Parameters

    • idx: number

      Node index

    Returns T | undefined

    Parent element

init

  • init(array?: Array<T>): void

  • Initialise a heap, sorting nodes

    Parameters

    • Optional array: Array<T>

      Optional initial state array

    Returns void

isEmpty

  • isEmpty(): boolean

  • Test if the heap has no elements.

    Returns boolean

    True if no elements on the heap

iterator

  • iterator(): this

  • Returns an iterator. To comply with Java interface.

    Returns this

leafs

  • leafs(): T[]

  • Get the leafs of the tree (no children nodes)

    Returns T[]

peek

  • peek(): T | undefined

  • Top node. Aliases: element. Same as: top(1)[0]

    Returns T | undefined

    Top node

pop

  • pop(): T | undefined

  • Extract the top node (root). Aliases: poll.

    Returns T | undefined

    Extracted top node, undefined if empty

push

  • push(...elements: Array<T>): boolean

  • Pushes element(s) to the heap.

    Parameters

    • Rest ...elements: Array<T>

      Elements to insert

    Returns boolean

    True if elements are present

pushpop

  • pushpop(element: T): T

  • Same as push & pop in sequence, but faster

    Parameters

    • element: T

      Element to insert

    Returns T

    Extracted top node

remove

  • remove(o?: T, fn?: IsEqual<T>): boolean

  • Remove an element from the heap.

    Parameters

    • Optional o: T

      Element to be found

    • Default value fn: IsEqual<T> = Heap.defaultIsEqual

      Optional function to compare

    Returns boolean

    True if the heap was modified

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

size

  • size(): number

  • Size of the heap

    Returns number

toArray

  • toArray(): Array<T>

  • Clone the heap's internal array

    Returns Array<T>

toString

  • toString(): string

  • String output, call to Array.prototype.toString()

    Returns string

top

  • top(n?: number): Array<T>

  • Return the top (highest value) N elements of the heap.

    Parameters

    • Default value n: number = 1

      Number of elements.

    Returns Array<T>

    Array of length <= N.

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

Static getChildrenIndexOf

  • getChildrenIndexOf(idx: number): Array<number>

  • Gets children indices for given index.

    Parameters

    • idx: number

      Parent index

    Returns Array<number>

    Array of children indices

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

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

Static heapbottom

  • heapbottom<N>(heapArr: Array<N>, n?: number, compare?: Comparator<N>): N[]

  • Return the n least valuable elements

    Type parameters

    • N

    Parameters

    • heapArr: Array<N>

      Array, should be a heap

    • Default value n: number = 1

      Max number of elements

    • Optional compare: Comparator<N>

      Optional compare function

    Returns N[]

    Elements

Static heapify

  • Converts an array into an array-heap

    Type parameters

    • N

    Parameters

    • arr: Array<N>

      Array to be modified

    • Optional compare: Comparator<N>

      Optional compare function

    Returns Heap<N>

    For convenience, it returns a Heap instance

Static heappop

  • heappop<N>(heapArr: Array<N>, compare?: Comparator<N>): undefined | N

  • Extract the peek of an array-heap

    Type parameters

    • N

    Parameters

    • heapArr: Array<N>

      Array to be modified, should be a heap

    • Optional compare: Comparator<N>

      Optional compare function

    Returns undefined | N

    Returns the extracted peek

Static heappush

  • heappush<N>(heapArr: Array<N>, item: N, compare?: Comparator<N>): void

  • Pushes a item into an array-heap

    Type parameters

    • N

    Parameters

    • heapArr: Array<N>

      Array to be modified, should be a heap

    • item: N

      Item to push

    • Optional compare: Comparator<N>

      Optional compare function

    Returns void

Static heappushpop

  • heappushpop<N>(heapArr: Array<N>, item: N, compare?: Comparator<N>): N

  • Push followed by pop, faster

    Type parameters

    • N

    Parameters

    • heapArr: Array<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

Static heapreplace

  • heapreplace<N>(heapArr: Array<N>, item: N, compare?: Comparator<N>): N

  • Replace peek with item

    Type parameters

    • N

    Parameters

    • heapArr: Array<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

Static heaptop

  • heaptop<N>(heapArr: Array<N>, n?: number, compare?: Comparator<N>): N[]

  • Return the n most valuable elements

    Type parameters

    • N

    Parameters

    • heapArr: Array<N>

      Array, should be a heap

    • Default value n: number = 1

      Max number of elements

    • Optional compare: Comparator<N>

      Optional compare function

    Returns N[]

    Elements

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

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

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

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

Static print

  • print<N>(heap: Heap<N>): string

  • Prints a heap.

    Type parameters

    • N

    Parameters

    • heap: Heap<N>

      Heap to be printed

    Returns string

Legend

  • Class with type parameter
  • Constructor
  • Property
  • Method
  • Accessor
  • Variable
  • Type alias with type parameter
  • Static method

Generated using TypeDoc