GenericFibonacciHeap (JGraphT : a free Java graph library)

java.lang.Object
- org.jgrapht.util.GenericFibonacciHeap<K,T>

Type Parameters:

K - key type

T - data type
```
public class GenericFibonacciHeap<K,T>
extends Object
```
A Fibonacci heap data structure with a custom comparator. 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.
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.

Author:

Nathan Fiedler, Dimitrios Michail

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

class GenericFibonacciHeap.Node
The Fibonacci heap node.

Nested Classes
Modifier and Type	Class and Description
`class`	`GenericFibonacciHeap.Node` The Fibonacci heap node.

Constructor Summary

Constructors
Constructor and Description

GenericFibonacciHeap(Comparator<K> comparator)
Constructs an empty heap.

Constructors
Constructor and Description
`GenericFibonacciHeap(Comparator<K> comparator)` Constructs an empty heap.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`clear()` Removes all elements from this heap.
`GenericFibonacciHeap.Node`	`insert(K key, T data)` Inserts a new element into the heap.
`boolean`	`isEmpty()` Tests if the Fibonacci heap is empty or not.
`GenericFibonacciHeap.Node`	`min()` Returns the smallest element in the heap.
`GenericFibonacciHeap.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.
`String`	`toString()` Creates a String representation of this Fibonacci heap.
`static <K,T> GenericFibonacciHeap<K,T>`	`union(GenericFibonacciHeap<K,T> h1, GenericFibonacciHeap<K,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
  - GenericFibonacciHeap
```
public GenericFibonacciHeap(Comparator<K> comparator)
```
    Constructs an empty heap.
    
    Parameters:
    
    comparator - the comparator for key comparisons
- 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.
  - insert
```
public GenericFibonacciHeap.Node insert(K key,
                                        T data)
```
    Inserts a new 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:
    
    key - the key
    
    data - the value
    
    Returns:
    
    The new heap node
  - min
```
public GenericFibonacciHeap.Node 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 GenericFibonacciHeap.Node 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 <K,T> GenericFibonacciHeap<K,T> union(GenericFibonacciHeap<K,T> h1,
                                                    GenericFibonacciHeap<K,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. The method assumes that both heaps use the same comparator, otherwise the behavior is undefined.
    Running time: $O(1)$ actual
    
    Type Parameters:
    
    K - type of key stored in the heap
    
    T - type of data stored in the heap
    
    Parameters:
    
    h1 - first heap
    
    h2 - second heap
    
    Returns:
    
    new heap containing h1 and h2
  - toString
```
public String toString()
```
    Creates a String representation of this Fibonacci heap.
    
    Overrides:
    
    toString in class Object
    
    Returns:
    
    String of this.

Class GenericFibonacciHeap<K,T>

Nested Class Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

GenericFibonacciHeap

Method Detail

isEmpty

clear

insert

min

removeMin

size

union

toString