
MATES 3.0rc2  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.mates.util.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. It was altered and imported to MATES by Evan Sultanik.
Nested Class Summary  
static class 
FibonacciHeap.Node
Implements a node of the Fibonacci heap. 
Constructor Summary  
FibonacciHeap()
Constructs a minFibonacciHeap object that contains no elements. 

FibonacciHeap(boolean is_min_heap)
Constructs a FibonacciHeap object that contains no elements. 
Method Summary  
protected void 
cascadingCut(FibonacciHeap.Node y)
Performs a cascading cut operation. 
void 
changeKey(FibonacciHeap.Node x,
double k)
Changes the key value for a heap node, given the new value to take on. 
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 
delete(FibonacciHeap.Node x)
Deletes a node from the heap given the reference to the node. 
java.lang.Object 
extract()
Extracts the extreme element of the heap (either the minimum or the maximum, depending on weather this is a min heap or a max heap). 
FibonacciHeap.Node 
extreme()
Returns the smallest element in the heap if this is a min heap, or the largest if this is a max heap. 
void 
insert(FibonacciHeap.Node node,
double key)
Inserts a new data element into the heap. 
FibonacciHeap.Node 
insert(java.lang.Object object,
double key)
Inserts a new data element into the heap, creating a new node for it in the process. 
FibonacciHeap.Node 
insert(java.lang.Object object,
int key)
Inserts a new data element into the heap, creating a new node for it in the process. 
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 
removeExtreme()
Removes the smallest element from the heap if this is a min heap, or the largest element if this is a max 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()
public FibonacciHeap(boolean is_min_heap)
is_min_heap
 if true
, this heap will act as
a minheap; else it will act as a maxheap.Method Detail 
public boolean isEmpty()
Running time: O(1) actual
public void clear()
public void changeKey(FibonacciHeap.Node x, double k)
Running time: O(1) amortized
x
 node to change the key ofk
 new key value for node x
java.lang.IllegalArgumentException
 Thrown if k is larger than
x.key value and this is a min heap, or if k is
smaller than x.key and this is a max heap.public void delete(FibonacciHeap.Node x)
Running time: O(log n) amortized
x
 node to remove from heappublic FibonacciHeap.Node insert(java.lang.Object object, int key)
object
 an object to be associated with this data elementkey
 key value associated with data object
insert(FibonacciHeap.Node, double)
public FibonacciHeap.Node insert(java.lang.Object object, double key)
object
 an object to be associated with this data elementkey
 key value associated with data object
insert(FibonacciHeap.Node, double)
public 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 extreme()
Running time: O(1) actual
public java.lang.Object extract()
removeExtreme()
public FibonacciHeap.Node removeExtreme()
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
java.lang.IllegalArgumentException
 Thrown if h1
and h2
are not the same type of heap (i.e. if one
is a minheap and the other is a maxheap).public java.lang.String toString()
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

MATES 3.0rc2  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 