org.graphstream.algorithm.util

Class FibonacciHeap<K extends 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 Comparable<K>,V>
extends 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
• Adding a new 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

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.

add

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)

addAll

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:

IllegalArgumentException - if the new key is greater than the current.

Computational Complexity :

O(1) amortized running time