Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.jgrapht.util
Class FibonacciHeap<T>

    java.lang.Object
      org.jgrapht.util.FibonacciHeap<T>

    public class FibonacciHeap<T>

extends java.lang.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. It was imported to JGraphT with permission, courtesy of Nathan Fiedler.

Author:
  Nathan Fiedler

Constructor Summary
`FibonacciHeap()` Constructs a FibonacciHeap object that contains no elements.

Method Summary
`protected void` | `cascadingCut(FibonacciHeapNode<T> y)` Performs a cascading cut operation.
`void` | `clear()` Removes all elements from this heap.
`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(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.
`java.lang.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.

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.

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(FibonacciHeapNode<T> 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:
    `java.lang.IllegalArgumentException` - Thrown if k is larger than x.key value.

### delete

    public void delete(FibonacciHeapNode<T> 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(FibonacciHeapNode<T> node,
                       double key)

  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:
    `node` - new node to insert into heap
    `key` - key value associated with data object

### min

    public FibonacciHeapNode<T> min()

  Returns the smallest element in the heap. This smallest element is the one with the minimum key value.

  Running time: O(1) actual

  Returns:
    heap node with the smallest key

### removeMin

    public FibonacciHeapNode<T> removeMin()

  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:
    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

### union

    public static <T> FibonacciHeap<T> union(FibonacciHeap<T> h1,
                                             FibonacciHeap<T> 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

  Parameters:
    `h1` - first heap
    `h2` - second heap
  Returns:
    new heap containing h1 and h2

### toString

    public java.lang.String toString()

  Creates a String representation of this Fibonacci heap.

  Overrides:
    `toString` in class `java.lang.Object`
  Returns:
    String of this.

### cascadingCut

    protected void cascadingCut(FibonacciHeapNode<T> y)

  Performs a cascading cut operation. This cuts y from its parent and then does the same for its parent, and so on up the tree.

  Running time: O(log n); O(1) excluding the recursion

  Parameters:
    `y` - node to perform cascading cut on

### consolidate

    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.

  Running time: O(log n) amortized

### cut

    protected void cut(FibonacciHeapNode<T> x,
                       FibonacciHeapNode<T> y)

  The reverse of the link operation: removes x from the child list of y. This method assumes that min is non-null.

  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

### link

    protected void link(FibonacciHeapNode<T> y,
                        FibonacciHeapNode<T> x)

  Make node y a child of node x.

  Running time: O(1) actual

  Parameters:
    `y` - node to become child
    `x` - node to become parent

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD