public class JGraphFibonacciHeap
extends java.lang.Object
Modifier and Type | Class and Description |
---|---|
static class |
JGraphFibonacciHeap.Node
Implements a node of the Fibonacci heap.
|
Modifier and Type | Field and Description |
---|---|
protected JGraphFibonacciHeap.Node |
min |
protected java.util.Map |
nodes
Maps from elements to nodes
|
protected int |
size |
Constructor and Description |
---|
JGraphFibonacciHeap() |
Modifier and Type | Method and Description |
---|---|
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(java.lang.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.
|
protected java.util.Map nodes
protected JGraphFibonacciHeap.Node min
protected int size
public JGraphFibonacciHeap.Node getNode(java.lang.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 xjava.lang.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 heapprotected 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 parentCopyright (C) 2001-2009 JGraph Ltd. All rights reserved.