dastal - v5.0.0 / SkewHeap
A skew heap is a heap implemented as a binary tree (source).
A skew heap is a self-adjusting heap which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. Every operation that modifies the heap (e.g. push, pop, merge) is considered a merge and is done by using a skew heap merge.
Skew heaps can merge more quickly than binary heaps. This can seem contradictory, since skew heaps have no structural constraints and no guarantee that the height of the tree is logarithmic (i.e. balanced). However, amortized complexity analysis can demonstrate that all operations on a skew heap can be done in O(log(n). More specifically, the amortized complexity is known to be logφ(n) where φ is the golden ratio. This is approximately 1.44*log2(n).
| Property | Average | Worst |
|---|---|---|
| Space | O(n) | O(n) |
| Push | O(log n) | 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 SkewHeap<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 heap 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
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 |
|---|---|
element |
T |
boolean
true if the element was found, otherwise false.
▸ delete(element): boolean
Delete an element from the heap.
| Name | Type |
|---|---|
element |
T |
boolean
true if the element was found and deleted, otherwise false.
▸ merge(heap): SkewHeap<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> |
SkewHeap<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(value): number
Inserts an element into the heap (AKA insert, add).
| Name | Type |
|---|---|
value |
T |
number
The new size of the heap.
▸ pushPop(value): T
Insert an element and then remove the top of the heap.
| Name | Type |
|---|---|
value |
T |
T
The element at the top of the heap.
▸ replace(value): undefined | T
Remove the top of the heap and then insert a new element (AKA popPush).
| Name | Type |
|---|---|
value |
T |
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 |
|---|---|
curElement |
T |
newElement |
T |
boolean
true if curElement was found and updated, otherwise false.