Typed API (TypeDoc) / FibonacciHeap
Class: FibonacciHeap<E>
Defined in: heap.ts:315
Since
2.0.0
Type Parameters
E
E
Value type.
Implements
Constructors
Constructor
new FibonacciHeap<
E>(comparator,elements?):FibonacciHeap<E>
Defined in: heap.ts:338
Parameters
comparator
Comparator<E>
Ordering strategy.
elements?
Iterable<E, any, any>
Optional seed data.
Returns
FibonacciHeap<E>
Properties
comparator
comparator:
Comparator<E>
Defined in: heap.ts:331
Comparator used for equality/sort checks.
Implementation of
minNode
minNode:
FibonacciHeapNode<E>
Defined in: heap.ts:323
Current minimum node
Implementation of
rootList
rootList:
FibonacciHeapNode<E>
Defined in: heap.ts:319
List of root nodes of the FibonacciHeap
Implementation of
size
size:
number=0
Defined in: heap.ts:327
Current element count.
Implementation of
Methods
[iterator]()
[iterator]():
Iterator<E>
Defined in: heap.ts:753
Iterator for iterating through the values of the FibonacciHeapNodes.
Returns
Iterator<E>
Implementation of
IFibonacciHeap.[iterator]
add()
add(
e):FibonacciHeapNode<E>
Defined in: heap.ts:393
Append an element.
Parameters
e
E
Returns
Remarks
Complexity: Amortized O(1) unless stated otherwise.
Implementation of
addAll()
addAll(
collection):void
Defined in: heap.ts:400
Append every element from another collection.
Parameters
collection
ICollection<E>
Returns
void
Remarks
Complexity: O(n + m) where m is collection.size.
Implementation of
clear()
clear():
void
Defined in: heap.ts:529
Clears the FibonacciHeap, bei undefining the min node and rootList.
Returns
void
Remarks
Complexity: O(1)
Implementation of
contains()
contains(
element):boolean
Defined in: heap.ts:380
Test membership using the comparator when available.
Parameters
element
E
Returns
boolean
Remarks
Complexity: O(n) worst case
Implementation of
decreaseKey()
decreaseKey(
node,newValue):void
Defined in: heap.ts:427
Decrease a node's key and bubble it up if necessary.
Parameters
node
Target node handle.
newValue
E
New value (must compare <= old value). Pass null/undefined to mark the node as the next minimum.
Returns
void
Throws
When newValue is greater than the current value.
Remarks
Complexity: O(1) amortized
Implementation of
delete()
delete(
e):FibonacciHeapNode<E>
Defined in: heap.ts:413
Delete a node using its handle.
Parameters
e
Node handle obtained from insert.
Returns
Removed node.
Remarks
Complexity: O(log n) amortized
Implementation of
extractChildren()
extractChildren(
node):CyclicDoublyLinkedList<FibonacciHeapNode<E>>
Defined in: heap.ts:564
Return the child list of a node.
Parameters
node
Parent node.
Returns
CyclicDoublyLinkedList<FibonacciHeapNode<E>>
Cyclic list of children.
Implementation of
IFibonacciHeap.extractChildren
extractMin()
extractMin():
FibonacciHeapNode<E>
Defined in: heap.ts:462
Returns and removes the minimum node from the FibonacciHeap.
Returns
Removed minimum node.
Remarks
Complexity: O(log n) amortized
Implementation of
extractNeighbours()
extractNeighbours(
node,includeSelf):CyclicDoublyLinkedList<FibonacciHeapNode<E>>
Defined in: heap.ts:541
Collect sibling nodes adjacent to the provided node.
Parameters
node
Starting node.
includeSelf
boolean = false
Whether to include node in the output.
Returns
CyclicDoublyLinkedList<FibonacciHeapNode<E>>
Cyclic list of neighbour nodes.
Implementation of
IFibonacciHeap.extractNeighbours
insert()
insert(
element):FibonacciHeapNode<E>
Defined in: heap.ts:354
Insert a value and return its node handle.
Parameters
element
E
Value to insert.
Returns
Newly created node.
Remarks
Complexity: O(1)
Implementation of
isEmpty()
isEmpty():
boolean
Defined in: heap.ts:521
Check for emptiness.
Returns
boolean
true when size === 0.
Implementation of
minimum()
minimum():
FibonacciHeapNode<E>
Defined in: heap.ts:452
Returns the current minimum node in the FibonacciHeap.
Returns
Current minimum node.
Remarks
Complexity: O(1)
Implementation of
nodeIterator()
nodeIterator():
Generator<FibonacciHeapNode<E>,void,unknown>
Defined in: heap.ts:744
Iterator for iterating all FibonacciHeapNodes.
Returns
Generator<FibonacciHeapNode<E>, void, unknown>
remove()
remove(
target,isIndex):number|E
Defined in: heap.ts:795
Remove by value or index.
Parameters
target
number | E
isIndex
boolean = true
When true, treat e as index.
Returns
number | E
Removed element or index of removal.
Throws
If neither argument nor existing comparator are set.
Remarks
Complexity: O(n) worst case.
Implementation of
reverseIterator()
reverseIterator():
Generator<E>
Defined in: heap.ts:772
Reverse iterate through the values of the FibonacciHeap.
Returns
Generator<E>
Implementation of
IFibonacciHeap.reverseIterator
sort()
sort(
cmp?):void
Defined in: heap.ts:784
This sort function changes the comparator (!), if one is given as parameter.
Parameters
cmp?
Comparator<E>
Returns
void
Implementation of
union()
union(
heap):void
Defined in: heap.ts:497
Merge another heap into this one.
Parameters
heap
to merge in the current one
Returns
void
Remarks
Complexity: O(1)