BinaryHeap

Class

Binary Heap Implementation that implements the 'insert' and 'remove' methods of the IBinaryHeap interface. Example use is for k-way merge sorting of k sorted arrays. Performance is O(n log n) for initialization (could be further optimized), O(log n) for insertion and O(log n) for deletion

Implements

Constructors

  • new BinaryHeap(nodes: Array<INode<>>, cmptr: comparator<>, direction: "ASC" | "DESC") : BinaryHeap

Constructor Parameters

Parameter Type Default Notes
nodes Required Array<INode<>>
cmptr Required comparator<>
direction Optional "ASC" | "DESC" "ASC" as HeapDirection

Methods

Method Returns Notes
ReadonlyArray<INode<>>

Returns a readonly version of the heap as an array

void

Inserts node into binary heap

number

Returns number of nodes in heap

INode<> | null

Removes either the minimum or the maximum node, depending on heap implementation

heap

Class Method

Returns a readonly version of the heap as an array

  • heap() : ReadonlyArray<INode<>>

Returns

Readonly array representation of the heap

ReadonlyArray<INode<>>

insert

Class Method

Inserts node into binary heap

  • insert(node: INode<>) : void

Parameters

Parameter Type Default Notes
node Required INode<>

Returns

void

length

Class Method

Returns number of nodes in heap

  • length() : number

Returns

number of nodes

number

remove

Class Method

Removes either the minimum or the maximum node, depending on heap implementation

  • remove() : INode<> | null

Returns

the min/max node or null if heap is empty.

INode<> | null

Class defined in search/src/util/merge-sort/merge.ts:143