dastal - v5.0.0 / Heap
A specialized tree-based data structure that satisfies the heap property (source).
Heap property: For any given node N, the key (e.g. value) of N is greater than or equal to the key of its children.
In a heap, the highest priority element (relative to its ordering) is always stored at the root. However, a heap is not a sorted structure; it can be regarded as being partially ordered. The heap property only applies between a parent node and its descendants. There is no implied ordering between siblings or cousins and no implied sequence for an ordered traversal.
A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest priority. In the sense, it can be used to implement a priority queue.
Iterate
- Iterate the heap: {@link [Symbol.iterator]}
- Iterate the heap in sorted order: sorted
Get
- Get the size of the heap: size
- Get the top element: peek
- Check if the heap contains a given element: contains
- Get the heap's sorting method: comparator
Set
- Update an element: update
Add
Remove
Add & Remove
- Add and then remove the top element: pushPop
- Remove the top element and then add an element: replace
| Name |
|---|
T |
-
Collection<T>
-
Sorted<T>
↳ Heap
- [iterator]
- addAll
- clear
- comparator
- contains
- delete
- merge
- peek
- pop
- push
- pushPop
- replace
- sorted
- update
• Readonly size: number
The number of elements in the collection.
src/collection/collection.ts:5
▸ [iterator](): Iterator<T, any, undefined>
Iterator<T, any, undefined>
node_modules/typescript/lib/lib.es2015.iterable.d.ts:51
▸ addAll(elements): number
Insert a set of elements into the heap.
| Name | Type | Description |
|---|---|---|
elements |
Iterable<T> |
The elements to insert. |
number
The new size of the list.
▸ clear(): void
Removes all elements.
void
▸ comparator(): CompareFn<T>
CompareFn<T>
The function with which elements are sorted
▸ contains(element): boolean
Check if an element is in the heap.
| Name | Type | Description |
|---|---|---|
element |
T |
The element to find. |
boolean
true if the element was found, otherwise false.
▸ delete(element): boolean
Delete an element from the heap.
| Name | Type | Description |
|---|---|---|
element |
T |
The element to delete. |
boolean
true if the element was found and deleted, otherwise false.
▸ merge(heap): Heap<T>
Join with a different heap and modify the existing heap to contain elements of both. Does not modify the input.
| Name | Type | Description |
|---|---|---|
heap |
Heap<T> | The heap to join with. |
Heap<T>
The heap.
▸ peek(): undefined | T
Retrieves, but does not remove, the top of the heap.
undefined | T
The element at the top of the heap or undefined if empty.
▸ pop(): undefined | T
Remove the top of the heap (AKA extract).
undefined | T
The element at the top of the heap or undefined if empty.
▸ push(element): number
Inserts an element into the heap (AKA insert, add).
| Name | Type | Description |
|---|---|---|
element |
T |
The element to be inserted. |
number
The new size of the heap.
▸ pushPop(element): T
Insert an element and then remove the top of the heap.
| Name | Type | Description |
|---|---|---|
element |
T |
The element to be inserted. |
T
The element at the top of the heap.
▸ replace(element): undefined | T
Remove the top of the heap and then insert a new element (AKA popPush).
| Name | Type | Description |
|---|---|---|
element |
T |
The element to be inserted. |
undefined | T
The element at the top of the heap or undefined if empty.
▸ 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 | Description |
|---|---|---|
curElement |
T |
The element to update. |
newElement |
T |
The new element to insert. |
boolean
true if curElement was found and updated, otherwise false.