|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg._3pq.jgrapht.util.FibonacciHeap
public class FibonacciHeap
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.
Nested Class Summary | |
---|---|
static class |
FibonacciHeap.Node
Implements a node of the Fibonacci heap. |
Constructor Summary | |
---|---|
FibonacciHeap()
Constructs a FibonacciHeap object that contains no elements. |
Method Summary | |
---|---|
protected void |
cascadingCut(FibonacciHeap.Node y)
Performs a cascading cut operation. |
void |
clear()
Removes all elements from this heap. |
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. |
protected void |
cut(FibonacciHeap.Node x,
FibonacciHeap.Node y)
The reverse of the link operation: removes x from the child list of y. |
void |
decreaseKey(FibonacciHeap.Node x,
double k)
Decreases the key value for a heap node, given the new value to take on. |
void |
delete(FibonacciHeap.Node x)
Deletes a node from the heap given the reference to the node. |
void |
insert(FibonacciHeap.Node 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(FibonacciHeap.Node y,
FibonacciHeap.Node x)
Make node y a child of node x. |
FibonacciHeap.Node |
min()
Returns the smallest element in the heap. |
FibonacciHeap.Node |
removeMin()
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. |
java.lang.String |
toString()
Creates a String representation of this Fibonacci heap. |
static FibonacciHeap |
union(FibonacciHeap h1,
FibonacciHeap h2)
Joins two Fibonacci heaps into a new one. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public FibonacciHeap()
Method Detail |
---|
public boolean isEmpty()
Running time: O(1) actual
public void clear()
public void decreaseKey(FibonacciHeap.Node x, double k)
Running time: O(1) amortized
x
- node to decrease the key ofk
- new key value for node x
java.lang.IllegalArgumentException
- Thrown if k is larger than x.key
value.public void delete(FibonacciHeap.Node x)
Running time: O(log n) amortized
x
- node to remove from heappublic void insert(FibonacciHeap.Node node, double key)
Running time: O(1) actual
node
- new node to insert into heapkey
- key value associated with data objectpublic FibonacciHeap.Node min()
Running time: O(1) actual
public FibonacciHeap.Node removeMin()
Running time: O(log n) amortized
public int size()
Running time: O(1) actual
public static FibonacciHeap union(FibonacciHeap h1, FibonacciHeap h2)
Running time: O(1) actual
h1
- first heaph2
- second heap
public java.lang.String toString()
toString
in class java.lang.Object
protected void cascadingCut(FibonacciHeap.Node y)
Running time: O(log n); O(1) excluding the recursion
y
- node to perform cascading cut onprotected void consolidate()
Running time: O(log n) amortized
protected void cut(FibonacciHeap.Node x, FibonacciHeap.Node y)
Running time: O(1)
x
- child of y to be removed from y's child listy
- parent of x about to lose a childprotected void link(FibonacciHeap.Node y, FibonacciHeap.Node x)
Running time: O(1) actual
y
- node to become childx
- node to become parent
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |