|
JGraph |
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.jgraph.algebra.JGraphFibonacciHeap
public class JGraphFibonacciHeap
This class implements a priority queue.
Nested Class Summary | |
---|---|
static class |
JGraphFibonacciHeap.Node
Implements a node of the Fibonacci heap. |
Field Summary | |
---|---|
protected JGraphFibonacciHeap.Node |
min
|
protected Map |
nodes
Maps from elements to nodes |
protected int |
size
|
Constructor Summary | |
---|---|
JGraphFibonacciHeap()
|
Method Summary | |
---|---|
protected void |
cascadingCut(JGraphFibonacciHeap.Node y)
Performs a cascading cut operation. |
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(JGraphFibonacciHeap.Node x,
JGraphFibonacciHeap.Node y)
The reverse of the link operation: removes x from the child list of y. |
void |
decreaseKey(JGraphFibonacciHeap.Node x,
double k)
Decreases the key value for a heap node, given the new value to take on. |
void |
delete(JGraphFibonacciHeap.Node x)
Deletes a node from the heap given the reference to the node. |
JGraphFibonacciHeap.Node |
getNode(Object element,
boolean create)
Returns the node that represents element. |
void |
insert(JGraphFibonacciHeap.Node node,
double key)
Inserts a new data element into the heap. |
boolean |
isEmpty()
|
protected void |
link(JGraphFibonacciHeap.Node y,
JGraphFibonacciHeap.Node x)
Make node y a child of node x. |
JGraphFibonacciHeap.Node |
min()
Returns the smallest element in the heap. |
JGraphFibonacciHeap.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. |
static JGraphFibonacciHeap |
union(JGraphFibonacciHeap h1,
JGraphFibonacciHeap h2)
Joins two Fibonacci heaps into a new one. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected Map nodes
protected JGraphFibonacciHeap.Node min
protected int size
Constructor Detail |
---|
public JGraphFibonacciHeap()
Method Detail |
---|
public JGraphFibonacciHeap.Node getNode(Object element, boolean create)
public boolean isEmpty()
public void decreaseKey(JGraphFibonacciHeap.Node x, double k)
Running time: O(1) amortized
x
- node to decrease the key ofk
- new key value for node x
IllegalArgumentException
- Thrown if k is larger than x.key value.public void delete(JGraphFibonacciHeap.Node x)
Running time: O(log n) amortized
x
- node to remove from heappublic void insert(JGraphFibonacciHeap.Node node, double key)
Running time: O(1) actual
node
- new node to insert into heapkey
- key value associated with data objectpublic JGraphFibonacciHeap.Node min()
Running time: O(1) actual
public JGraphFibonacciHeap.Node removeMin()
Running time: O(log n) amortized
public int size()
Running time: O(1) actual
public static JGraphFibonacciHeap union(JGraphFibonacciHeap h1, JGraphFibonacciHeap h2)
Running time: O(1) actual
h1
- first heaph2
- second heap
protected void cascadingCut(JGraphFibonacciHeap.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(JGraphFibonacciHeap.Node x, JGraphFibonacciHeap.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(JGraphFibonacciHeap.Node y, JGraphFibonacciHeap.Node x)
Running time: O(1) actual
y
- node to become childx
- node to become parent
|
JGraph |
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |