Class: BinomialHeap<T>
Defined in: src/sdk/utils/datastructures/BinomialHeap.ts:26
A binominal 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 (amortized to constant time in the case of insertions). Merges are also supported, with destructive merges performed in logarithmic time.
Type Parameters
| Type Parameter |
|---|
T |
Constructors
Constructor
new BinomialHeap<
T>(comparator):BinomialHeap<T>
Defined in: src/sdk/utils/datastructures/BinomialHeap.ts:47
Constructor.
Parameters
| Parameter | Type | Description |
|---|---|---|
comparator | (a, b) => 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
BinomialHeap<T>
Accessors
size
Get Signature
get size():
number
Defined in: src/sdk/utils/datastructures/BinomialHeap.ts:37
The number of elements contained in this heap.
Returns
number
Methods
clear()
clear():
this
Defined in: src/sdk/utils/datastructures/BinomialHeap.ts:145
Removes all elements from this heap.
Returns
this
This heap, after it has been cleared.
findMin()
findMin():
undefined|T
Defined in: src/sdk/utils/datastructures/BinomialHeap.ts:54
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.
insert()
insert(
element):this
Defined in: src/sdk/utils/datastructures/BinomialHeap.ts:99
Inserts an element into this heap.
Parameters
| Parameter | Type | Description |
|---|---|---|
element | T | The element to insert. |
Returns
this
This heap, after the element has been inserted.
merge()
merge<
U>(other,destructive):this
Defined in: src/sdk/utils/datastructures/BinomialHeap.ts:123
Merges this heap with another one. The merge can either be non-destructive or destructive. A non-destructive merge preserves the other heap. A destructive merge clears the other heap. A destructive merge takes O(log N) time while a non-destructive merge takes O(M + log N) time, where N is either the size of this heap or the size of the other heap, whichever is larger, and M is the size of the other heap. The difference stems from the need to copy the other heap in a non-destructive merge. Note that the result of this operation is only valid if the two heaps have equivalent comparator functions.
Type Parameters
| Type Parameter |
|---|
U |
Parameters
| Parameter | Type | Default value | Description |
|---|---|---|---|
other | BinomialHeap<U> | undefined | The heap to merge into this one. |
destructive | boolean | false | Whether to perform a destructive merge. False by default. |
Returns
this
This heap, after the merge has been completed.
removeMin()
removeMin():
undefined|T
Defined in: src/sdk/utils/datastructures/BinomialHeap.ts:62
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.