org._3pq.jgrapht.util
Class FibonacciHeap
java.lang.Object
org._3pq.jgrapht.util.FibonacciHeap
public class FibonacciHeap
extends java.lang.Object
This class implements a Fibonacci heap data structure. Much of the code in
this class is based on the algorithms in the "Introduction to Algorithms"
by Cormen, Leiserson, and Rivest in Chapter 21. The amortized running time
of most of these methods is O(1), making it a very fast data structure.
Several have an actual running time of O(1). removeMin() and delete() have
O(log n) amortized running times because they do the heap consolidation. If
you attempt to store nodes in this heap with key values of -Infinity
(Double.NEGATIVE_INFINITY) the
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.
FibonacciHeap() - Constructs a FibonacciHeap object that contains no elements.
|
FibonacciHeap
public FibonacciHeap()
Constructs a FibonacciHeap object that contains no elements.
cascadingCut
protected void cascadingCut(FibonacciHeap.Node y)
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
y
- node to perform cascading cut on
clear
public void clear()
Removes all elements from this heap.
consolidate
protected void consolidate()
Consolidates the trees in the heap by joining trees of equal degree
until there are no more trees of equal degree in the root list.
Running time: O(log n) amortized
cut
protected void cut(FibonacciHeap.Node x,
FibonacciHeap.Node y)
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)
x
- child of y to be removed from y's child listy
- parent of x about to lose a child
decreaseKey
public void decreaseKey(FibonacciHeap.Node x,
double k)
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
x
- node to decrease the key ofk
- new key value for node x
delete
public void delete(FibonacciHeap.Node x)
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
x
- node to remove from heap
insert
public void insert(FibonacciHeap.Node node,
double key)
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
node
- new node to insert into heapkey
- key value associated with data object
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
- true if the heap is empty, false otherwise
min
public FibonacciHeap.Node min()
Returns the smallest element in the heap. This smallest element is the
one with the minimum key value.
Running time: O(1) actual
- heap node with the smallest key
removeMin
public FibonacciHeap.Node 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
- 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
- number of elements in the heap
toString
public String toString()
Creates a String representation of this Fibonacci heap.
union
public static FibonacciHeap union(FibonacciHeap h1,
FibonacciHeap h2)
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
h1
- first heaph2
- second heap
- new heap containing h1 and h2