Class FibonacciHeap<T>
delete()
operation may fail to
remove the correct element.
Note that this implementation is not synchronized. If multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set.
This class was originally developed by Nathan Fiedler for the GraphMaker project. It was imported to JGraphT with permission, courtesy of Nathan Fiedler.
- Author:
- Nathan Fiedler
-
Constructor Summary
ConstructorsConstructorDescriptionConstructs a FibonacciHeap object that contains no elements. -
Method Summary
Modifier and TypeMethodDescriptionprotected void
Performs a cascading cut operation.void
clear()
Removes all elements from this heap.protected void
protected void
cut
(FibonacciHeapNode<T> x, FibonacciHeapNode<T> y) The reverse of the link operation: removes x from the child list of y.void
decreaseKey
(FibonacciHeapNode<T> x, double k) Decreases the key value for a heap node, given the new value to take on.void
delete
(FibonacciHeapNode<T> x) Deletes a node from the heap given the reference to the node.void
insert
(FibonacciHeapNode<T> node, double key) Inserts a new data element into the heap.boolean
isEmpty()
Tests if the Fibonacci heap is empty or not.protected void
link
(FibonacciHeapNode<T> y, FibonacciHeapNode<T> x) Make node y a child of node x.min()
Returns the smallest element in the heap.Removes the smallest element from the heap.int
size()
Returns the size of the heap which is measured in the number of elements contained in the heap.toString()
Creates a String representation of this Fibonacci heap.static <T> FibonacciHeap
<T> union
(FibonacciHeap<T> h1, FibonacciHeap<T> h2) Joins two Fibonacci heaps into a new one.
-
Constructor Details
-
FibonacciHeap
public FibonacciHeap()Constructs a FibonacciHeap object that contains no elements.
-
-
Method Details
-
isEmpty
public boolean isEmpty()Tests if the Fibonacci heap is empty or not. Returns true if the heap is empty, false otherwise.Running time: O(1) actual
- Returns:
- true if the heap is empty, false otherwise
-
clear
public void clear()Removes all elements from this heap. -
decreaseKey
Decreases the key value for a heap node, given the new value to take on. The structure of the heap may be changed and will not be consolidated.Running time: O(1) amortized
- Parameters:
x
- node to decrease the key ofk
- new key value for node x- Throws:
IllegalArgumentException
- Thrown if k is larger than x.key value.
-
delete
Deletes a node from the heap given the reference to the node. The trees in the heap will be consolidated, if necessary. This operation may fail to remove the correct element if there are nodes with key value -Infinity.Running time: O(log n) amortized
- Parameters:
x
- node to remove from heap
-
insert
Inserts a new data element into the heap. No heap consolidation is performed at this time, the new node is simply inserted into the root list of this heap.Running time: O(1) actual
- Parameters:
node
- new node to insert into heapkey
- key value associated with data object
-
min
Returns the smallest element in the heap. This smallest element is the one with the minimum key value.Running time: O(1) actual
- Returns:
- heap node with the smallest key
-
removeMin
Removes the smallest element from the heap. This will cause the trees in the heap to be consolidated, if necessary.Running time: O(log n) amortized
- Returns:
- node with the smallest key
-
size
public int size()Returns the size of the heap which is measured in the number of elements contained in the heap.Running time: O(1) actual
- Returns:
- number of elements in the heap
-
union
Joins two Fibonacci heaps into a new one. No heap consolidation is performed at this time. The two root lists are simply joined together.Running time: O(1) actual
- Parameters:
h1
- first heaph2
- second heap- Returns:
- new heap containing h1 and h2
-
toString
Creates a String representation of this Fibonacci heap. -
cascadingCut
Performs a cascading cut operation. This cuts y from its parent and then does the same for its parent, and so on up the tree.Running time: O(log n); O(1) excluding the recursion
- Parameters:
y
- node to perform cascading cut on
-
consolidate
protected void consolidate() -
cut
The reverse of the link operation: removes x from the child list of y. This method assumes that min is non-null.Running time: O(1)
- Parameters:
x
- child of y to be removed from y's child listy
- parent of x about to lose a child
-
link
Make node y a child of node x.Running time: O(1) actual
- Parameters:
y
- node to become childx
- node to become parent
-