Class: BinaryHeap<T>
A binary min-heap. Each element added to the heap is ordered according to the value of an assigned key relative to the keys of the other elements in the heap. The relative values of element keys are defined by a supplied comparator function. Retrieval of the element with the smallest key (minimum element) is performed in constant time. Removal of the minimum element and insertions are performed in logarithmic time. Additionally, this type of heap supports combined insertion and removal operations (in either order) which are slightly more efficient than chaining the two operations separately.
Type parameters
| Name |
|---|
T |
Constructors
constructor
• new BinaryHeap<T>(comparator): BinaryHeap<T>
Constructor.
Type parameters
| Name |
|---|
T |
Parameters
| Name | Type | Description |
|---|---|---|
comparator | (a: T, b: T) => number | The function that this heap uses to compare the keys of its elements. The function returns 0 if a and b share the same key, a negative number if a has a lower key than b, and a positive number if a has a greater key than b. |
Returns
BinaryHeap<T>
Defined in
src/sdk/utils/datastructures/BinaryHeap.ts:24
Accessors
size
• get size(): number
The number of elements contained in this heap.
Returns
number
Defined in
src/sdk/utils/datastructures/BinaryHeap.ts:14
Methods
clear
▸ clear(): this
Removes all elements from this heap.
Returns
this
This heap, after it has been cleared.
Defined in
src/sdk/utils/datastructures/BinaryHeap.ts:95
findMin
▸ findMin(): undefined | T
Finds the element in this heap with the smallest key.
Returns
undefined | T
The element in this heap with the smallest key, or undefined if this heap is empty.
Defined in
src/sdk/utils/datastructures/BinaryHeap.ts:31
insert
▸ insert(element): this
Inserts an element into this heap.
Parameters
| Name | Type | Description |
|---|---|---|
element | T | The element to insert. |
Returns
this
This heap, after the element has been inserted.
Defined in
src/sdk/utils/datastructures/BinaryHeap.ts:58
insertAndRemoveMin
▸ insertAndRemoveMin(element): T
Inserts an element into this heap, then removes the element with the smallest key.
Parameters
| Name | Type | Description |
|---|---|---|
element | T | The element to insert. |
Returns
T
The removed element.
Defined in
src/sdk/utils/datastructures/BinaryHeap.ts:70
removeMin
▸ removeMin(): undefined | T
Removes and returns the element in this heap with the smallest key.
Returns
undefined | T
The removed element, or undefined if this heap is empty.
Defined in
src/sdk/utils/datastructures/BinaryHeap.ts:39
removeMinAndInsert
▸ removeMinAndInsert(element): undefined | T
Removes the element in this heap with the smallest key, then inserts a new element.
Parameters
| Name | Type | Description |
|---|---|---|
element | T | The element to insert. |
Returns
undefined | T
The removed element, or undefined if this heap was empty before the new element was inserted.
Defined in
src/sdk/utils/datastructures/BinaryHeap.ts:83