org.graphstream.algorithm.util

## Class FibonacciHeap<K extends java.lang.Comparable<K>,V>

• java.lang.Object
• org.graphstream.algorithm.util.FibonacciHeap<K,V>
• Type Parameters:
`K` - the type of the keys
`V` - the type of the values

```public class FibonacciHeap<K extends java.lang.Comparable<K>,V>
extends java.lang.Object```

Fibonacci heap is a data structure used mainly to implement priority queues. It stores pairs (key, value) in nodes. The structure is designed so that the following operations can be implemented efficiently:

• Finding the node with minimal key
• Extracting the node with minimal key
• Decreasing the key of a given node
• Merging two heaps
• Deleting a node

This implementation does not support directly the last operation, but there is a workaround. To delete a node, first decrease its key to something less than the current minimum, then just extract the minimum.

In order to compare keys, this implementation uses their natural order: they must implement `Comparable` interface. The values can be of any type.

### Example

``` FibonacciHeap<Integer, String> heap = new FibonacciHeap<Integer, String>();
// add some nodes and keep their references in order to be able to decrease
// their keys later
FibonacciHeap<Integer, String>.Node nodeA = heap.add(20, "A");
FibonacciHeap<Integer, String>.Node nodeB = heap.add(10, "B");
FibonacciHeap<Integer, String>.Node nodeC = heap.add(30, "C");
FibonacciHeap<Integer, String>.Node nodeD = heap.add(50, "D");
FibonacciHeap<Integer, String>.Node nodeE = heap.add(40, "E");

String s1 = heap.extractMin(); // "B"
String s2 = heap.getMinValue(); // "A"
heap.decreaseKey(nodeD, 5);
String s3 = heap.extractMin(); // "D"
//delete nodeC
int kMin = heap.getMinKey(); // 20
heap.decreaseKey(nodeC, kMin - 1);
String s4 = heap.extractMin(); // C
```
Author:
Stefan Balev
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
`class ` `FibonacciHeap.Node`
This class encapsulates pairs (key, value) in nodes stored in Fibonacci heaps.
• ### Constructor Summary

Constructors
Constructor and Description
`FibonacciHeap()`
Creates a new empty Fibonacci heap.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`FibonacciHeap.Node` ```add(K key, V value)```
Adds a new node containing the given key and value to the heap.
`void` `addAll(FibonacciHeap<K,V> heap)`
Merges two heaps.
`void` `clear()`
Removes all the nodes in the heap
`void` ```decreaseKey(FibonacciHeap.Node x, K key)```
Decreases the key of a given node
`V` `extractMin()`
Removes the node containing the minimal key from the heap.
`K` `getMinKey()`
Returns the minimal key in the heap.
`V` `getMinValue()`
Returns the value stored in the node containing the minimal key.
`boolean` `isEmpty()`
Checks if the heap is empty.
`int` `size()`
Returns the number of nodes in the heap.
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### FibonacciHeap

`public FibonacciHeap()`
Creates a new empty Fibonacci heap.
• ### Method Detail

• #### isEmpty

`public boolean isEmpty()`
Checks if the heap is empty.
Returns:
`true` if the heap is empty
Computational Complexity:
O(1)
• #### size

`public int size()`
Returns the number of nodes in the heap.
Returns:
the number of nodes in the heap
Computational Complexity:
O(1)
• #### clear

`public void clear()`
Removes all the nodes in the heap
Computational Complexity:
This operation can be done in O(1) but this implementation takes O(n) in order to facilitate the garbage collection.

```public FibonacciHeap.Node add(K key,
V value)```
Adds a new node containing the given key and value to the heap.
Parameters:
`key` - the key of the new node
`value` - the value of the new node
Returns:
a reference to the new node. Typically this reference is stored and used in subsequent calls to `decreaseKey(Node, Comparable)`
Computational Complexity:
O(1)

`public void addAll(FibonacciHeap<K,V> heap)`
Merges two heaps. Warning: this operation is destructive. This method empties the parameter `heap`.
Parameters:
`heap` - the heap to be merged with this heap
Computational Complexity:
O(1)
• #### getMinKey

`public K getMinKey()`
Returns the minimal key in the heap.
Returns:
the minimal key in the heap
Computational Complexity:
O(1)
• #### getMinValue

`public V getMinValue()`
Returns the value stored in the node containing the minimal key.
Returns:
the value stored in the node containing the minimal key
Computational Complexity:
O(1)
• #### extractMin

`public V extractMin()`
Removes the node containing the minimal key from the heap.
Returns:
the value stored in the removed node
Computational Complexity:
O(logn) amortized running time
• #### decreaseKey

```public void decreaseKey(FibonacciHeap.Node x,
K key)```
Decreases the key of a given node
Parameters:
`x` - the node whose key is to be decreased. Must be a reference returned by `add(Comparable, Object)`.
`key` - the new key
Throws:
`java.lang.IllegalArgumentException` - if the new key is greater than the current.
Computational Complexity:
O(1) amortized running time