public class FibonacciHeap<T> extends Object
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.
Constructor and Description 

FibonacciHeap()
Constructs a FibonacciHeap object that contains no elements.

Modifier and Type  Method and Description 

protected void 
cascadingCut(FibonacciHeapNode<T> y)
Performs a cascading cut operation.

void 
clear()
Removes all elements from this heap.

protected void 
consolidate() 
protected void 
cut(FibonacciHeapNode<T> x,
FibonacciHeapNode<T> y)
The reverse of the link operation: removes x from the child list of y.

void 
decreaseKey(FibonacciHeapNode<T> x,
double k)
Decreases the key value for a heap node, given the new value to take on.

void 
delete(FibonacciHeapNode<T> x)
Deletes a node from the heap given the reference to the node.

void 
insert(FibonacciHeapNode<T> 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(FibonacciHeapNode<T> y,
FibonacciHeapNode<T> x)
Make node y a child of node x.

FibonacciHeapNode<T> 
min()
Returns the smallest element in the heap.

FibonacciHeapNode<T> 
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.

String 
toString()
Creates a String representation of this Fibonacci heap.

static <T> FibonacciHeap<T> 
union(FibonacciHeap<T> h1,
FibonacciHeap<T> h2)
Joins two Fibonacci heaps into a new one.

public FibonacciHeap()
public boolean isEmpty()
Running time: O(1) actual
public void clear()
public void decreaseKey(FibonacciHeapNode<T> x, double k)
Running time: O(1) amortized
x
 node to decrease the key ofk
 new key value for node xIllegalArgumentException
 Thrown if k is larger than x.key
value.public void delete(FibonacciHeapNode<T> x)
Running time: O(log n) amortized
x
 node to remove from heappublic void insert(FibonacciHeapNode<T> node, double key)
Running time: O(1) actual
node
 new node to insert into heapkey
 key value associated with data objectpublic FibonacciHeapNode<T> min()
Running time: O(1) actual
public FibonacciHeapNode<T> removeMin()
Running time: O(log n) amortized
public int size()
Running time: O(1) actual
public static <T> FibonacciHeap<T> union(FibonacciHeap<T> h1, FibonacciHeap<T> h2)
Running time: O(1) actual
h1
 first heaph2
 second heappublic String toString()
protected void cascadingCut(FibonacciHeapNode<T> y)
Running time: O(log n); O(1) excluding the recursion
y
 node to perform cascading cut onprotected void consolidate()
protected void cut(FibonacciHeapNode<T> x, FibonacciHeapNode<T> 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(FibonacciHeapNode<T> y, FibonacciHeapNode<T> x)
Running time: O(1) actual
y
 node to become childx
 node to become parentCopyright © 2015. All rights reserved.