com.jgraph.algebra
public class JGraphFibonacciHeap extends Object
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 |
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. |
Running time: O(log n); O(1) excluding the recursion
Parameters: y node to perform cascading cut on
Running time: O(log n) amortized
Running time: O(1)
Parameters: x child of y to be removed from y's child list y parent of x about to lose a child
Running time: O(1) amortized
Parameters: x node to decrease the key of k new key value for node x
Throws: IllegalArgumentException Thrown if k is larger than x.key value.
Running time: O(log n) amortized
Parameters: x node to remove from heap
Running time: O(1) actual
Parameters: node new node to insert into heap key key value associated with data object
Running time: O(1) actual
Parameters: y node to become child x node to become parent
Running time: O(1) actual
Returns: heap node with the smallest key
Running time: O(log n) amortized
Returns: node with the smallest key
Running time: O(1) actual
Returns: number of elements in the heap
Running time: O(1) actual
Parameters: h1 first heap h2 second heap
Returns: new heap containing h1 and h2