V
 the type of the verticespublic class FibonacciHeap<V extends Vertible<V>> extends Object
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.
Constructor and Description 

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

FibonacciHeap(V[] vertices)
Constructs a FibonacciHeap object containing the elements of the specified array.

Modifier and Type  Method and Description 

void 
clear()
Removes all elements from this heap.

protected void 
consolidate()
Consolidates this Fibonacci heap by cascading cut.

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

void 
delete(V x)
Deletes a node from the heap given the reference to the node.

V 
extractMin()
Removes the smallest element from the heap.

void 
insert(V x)
Inserts a new data element into the heap.

boolean 
isEmpty()
Tests if the Fibonacci heap is empty or not.

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 <V extends Vertible<V>> 
union(FibonacciHeap<V> h1,
FibonacciHeap<V> h2)
Joins two Fibonacci heaps into a new one.

public FibonacciHeap()
public FibonacciHeap(V[] vertices)
vertices
 an array of vertices this heap shall consist ofpublic boolean isEmpty()
Running time: O(1) actual
public void clear()
public void decreaseKey(V 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(V x)
Running time: O(log n) amortized
x
 node to remove from heappublic void insert(V x)
Running time: O(1) actual
x
 data element to be inserted into this heappublic V extractMin()
Running time: O(log n) amortized
public int size()
Running time: O(1) actual
public String toString()
protected void consolidate()
public static <V extends Vertible<V>> FibonacciHeap<V> union(FibonacciHeap<V> h1, FibonacciHeap<V> h2)
Running time: O(1) actual
V
 class implementing Vertible
and representing the verticesh1
 first heaph2
 second heap