dastal - v5.0.0 / BinaryHeap
A binary heap is a heap implemented as a binary tree with an additional shape property (source).
Shape property: Must be a complete binary tree. This means all levels of the tree (except possibly the last one) are fully filled. If the last level of the tree is incomplete, the nodes of that level are filled from left to right.
| Property | Average | Worst |
|---|---|---|
| Space | O(n) | O(n) |
| Push | O(1) | O(log n) |
| Peek | O(1) | O(1) |
| Pop | O(log n) | O(log n) |
| Search | O(n) | O(n) |
| Name |
|---|
T |
- Heap<T>
- [iterator]
- addAll
- clear
- comparator
- contains
- delete
- merge
- peek
- pop
- push
- pushPop
- replace
- sorted
- update
• new BinaryHeap<T>(compareFn, elements?)
Instantiate a heap.
| Name |
|---|
T |
| Name | Type | Description |
|---|---|---|
compareFn |
CompareFn<T> | The function to determine the order of elements. |
elements? |
Iterable<T> |
A set of elements to initialize the list with. |
• get size(): number
The number of elements in the collection.
number
▸ [iterator](): Iterator<T, any, undefined>
Receive an iterator through the list.
Note: Unexpected behavior can occur if the collection is modified during iteration.
Iterator<T, any, undefined>
An iterator through the list
▸ addAll(elements): number
Insert a set of elements into the heap.
| Name | Type |
|---|---|
elements |
Iterable<T> |
number
▸ clear(): void
Removes all elements.
void
▸ comparator(): CompareFn<T>
CompareFn<T>
▸ contains(element): boolean
Check if an element is in the heap.
| Name | Type |
|---|---|
element |
T |
boolean
▸ delete(element): boolean
Delete an element from the heap.
| Name | Type |
|---|---|
element |
T |
boolean
▸ merge(heap): BinaryHeap<T>
Join with a different heap and modify the existing heap to contain elements of both. Does not modify the input.
| Name | Type |
|---|---|
heap |
Heap<T> |
BinaryHeap<T>
▸ peek(): undefined | T
Retrieves, but does not remove, the top of the heap.
undefined | T
▸ pop(): undefined | T
Remove the top of the heap (AKA extract).
undefined | T
▸ push(value): number
Inserts an element into the heap (AKA insert, add).
| Name | Type |
|---|---|
value |
T |
number
▸ pushPop(value): T
Insert an element and then remove the top of the heap.
| Name | Type |
|---|---|
value |
T |
T
▸ replace(value): undefined | T
Remove the top of the heap and then insert a new element (AKA popPush).
| Name | Type |
|---|---|
value |
T |
undefined | T
▸ sorted(): Iterable<T>
Iterate through the heap in sorted order.
Note: Unexpected behavior can occur if the collection is modified during iteration.
Iterable<T>
▸ update(curElement, newElement): boolean
Update a specific element.
| Name | Type |
|---|---|
curElement |
T |
newElement |
T |
boolean