FibonacciHeap

java.lang.Object
- org.mathIT.graphs.FibonacciHeap<V>

Type Parameters:

V - the type of the vertices
```
public class FibonacciHeap<V extends Vertible<V>>
extends Object
```
This class implements a Fibonacci heap data structure. Much of the code in this class is based on the algorithms in the "Introduction to Algorithms"by Cormen, Leiserson, and Rivest in Chapter 21. The amortized running time of most of these methods is O(1), making it a very fast data structure. Several have an actual running time of O(1). 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.

Version:

1.1

Author:

Nathan Fiedler

Constructor Summary

Constructors
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.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
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>> FibonacciHeap<V>`	`union(FibonacciHeap<V> h1, FibonacciHeap<V> h2)` Joins two Fibonacci heaps into a new one.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - FibonacciHeap
```
public FibonacciHeap()
```
    Constructs a FibonacciHeap object that contains no elements.
  - FibonacciHeap
```
public FibonacciHeap(V[] vertices)
```
    Constructs a FibonacciHeap object containing the elements of the specified array.
    
    Parameters:
    
    vertices - an array of vertices this heap shall consist of
- Method Detail
  - isEmpty
```
public boolean isEmpty()
```
    Tests if the Fibonacci heap is empty or not. Returns true if the heap is empty, false otherwise.
    Running time: O(1) actual
    
    Returns:
    
    true if the heap is empty, false otherwise
  - clear
```
public void clear()
```
    Removes all elements from this heap.
  - decreaseKey
```
public void decreaseKey(V x,
                        double k)
```
    Decreases the key value for a heap node, given the new value to take on. The structure of the heap may be changed and will not be consolidated.
    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.
  - delete
```
public void delete(V x)
```
    Deletes a node from the heap given the reference to the node. The trees in the heap will be consolidated, if necessary. This operation may fail to remove the correct element if there are nodes with key value -Infinity.
    Running time: O(log n) amortized
    
    Parameters:
    
    x - node to remove from heap
  - insert
```
public void insert(V x)
```
    Inserts a new data element into the heap. No heap consolidation is performed at this time, the new node is simply inserted into the root list of this heap.
    Running time: O(1) actual
    
    Parameters:
    
    x - data element to be inserted into this heap
  - extractMin
```
public V extractMin()
```
    Removes the smallest element from the heap. This will cause the trees in the heap to be consolidated, if necessary.
    Running time: O(log n) amortized
    
    Returns:
    
    data of the node with the smallest key
  - size
```
public int size()
```
    Returns the size of the heap which is measured in the number of elements contained in the heap.
    Running time: O(1) actual
    
    Returns:
    
    number of elements in the heap
  - toString
```
public String toString()
```
    Creates a String representation of this Fibonacci heap.
    
    Overrides:
    
    toString in class Object
    
    Returns:
    
    String of this.
  - consolidate
```
protected void consolidate()
```
    Consolidates this Fibonacci heap by cascading cut.
  - union
```
public static <V extends Vertible<V>> FibonacciHeap<V> union(FibonacciHeap<V> h1,
                                                             FibonacciHeap<V> h2)
```
    Joins two Fibonacci heaps into a new one. No heap consolidation is performed at this time. The two root lists are simply joined together.
    Running time: O(1) actual
    
    Type Parameters:
    
    V - class implementing Vertible and representing the vertices
    
    Parameters:
    
    h1 - first heap
    
    h2 - second heap
    
    Returns:
    
    new heap containing h1 and h2

Class FibonacciHeap<V extends Vertible<V>>

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

FibonacciHeap

FibonacciHeap

Method Detail

isEmpty

clear

decreaseKey

delete

insert

extractMin

size

toString

consolidate

union