org.mates.util
Class FibonacciHeap

java.lang.Object
  org.mates.util.FibonacciHeap

public class FibonacciHeap

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. It was altered and imported to MATES by Evan Sultanik.

Author:

Nathan Fiedler, John Sichi, Evan Sultanik

Nested Class Summary

static class

FibonacciHeap.Node Implements a node of the Fibonacci heap.

Constructor Summary

FibonacciHeap()
Constructs a min-FibonacciHeap object that contains no elements.

FibonacciHeap(boolean is_min_heap)
Constructs a FibonacciHeap object that contains no elements.

Method Summary

protected void	cascadingCut(FibonacciHeap.Node y) Performs a cascading cut operation.
void	changeKey(FibonacciHeap.Node x, double k) Changes the key value for a heap node, given the new value to take on.
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(FibonacciHeap.Node x, FibonacciHeap.Node y) The reverse of the link operation: removes x from the child list of y.
void	delete(FibonacciHeap.Node x) Deletes a node from the heap given the reference to the node.
java.lang.Object	extract() Extracts the extreme element of the heap (either the minimum or the maximum, depending on weather this is a min heap or a max heap).
FibonacciHeap.Node	extreme() Returns the smallest element in the heap if this is a min heap, or the largest if this is a max heap.
void	insert(FibonacciHeap.Node node, double key) Inserts a new data element into the heap.
FibonacciHeap.Node	insert(java.lang.Object object, double key) Inserts a new data element into the heap, creating a new node for it in the process.
FibonacciHeap.Node	insert(java.lang.Object object, int key) Inserts a new data element into the heap, creating a new node for it in the process.
boolean	isEmpty() Tests if the Fibonacci heap is empty or not.
protected void	link(FibonacciHeap.Node y, FibonacciHeap.Node x) Make node y a child of node x.
FibonacciHeap.Node	removeExtreme() Removes the smallest element from the heap if this is a min heap, or the largest element if this is a max 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 FibonacciHeap	union(FibonacciHeap h1, FibonacciHeap 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 min-FibonacciHeap object that contains no elements.

FibonacciHeap

public FibonacciHeap(boolean is_min_heap)

Constructs a FibonacciHeap object that contains no elements.

Parameters:

is_min_heap - if true, this heap will act as a min-heap; else it will act as a max-heap.

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.

changeKey

public void changeKey(FibonacciHeap.Node x,
                      double k)

Changes 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 change the key of

k - new key value for node x

Throws:

java.lang.IllegalArgumentException - Thrown if k is larger than x.key value and this is a min heap, or if k is smaller than x.key and this is a max heap.

delete

public void delete(FibonacciHeap.Node 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 FibonacciHeap.Node insert(java.lang.Object object,
                                 int key)

Inserts a new data element into the heap, creating a new node for it in the process. The integer key will be converted to a double.

Parameters:

object - an object to be associated with this data element

key - key value associated with data object

Returns:

the node created for this object

See Also:

insert(FibonacciHeap.Node, double)

insert

public FibonacciHeap.Node insert(java.lang.Object object,
                                 double key)

Inserts a new data element into the heap, creating a new node for it in the process.

Parameters:

object - an object to be associated with this data element

key - key value associated with data object

Returns:

the node created for this object

See Also:

insert(FibonacciHeap.Node, double)

insert

public void insert(FibonacciHeap.Node 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

extreme

public FibonacciHeap.Node extreme()

Returns the smallest element in the heap if this is a min heap, or the largest if this is a max heap.

Running time: O(1) actual

Returns:

heap node with the smallest key, if this is a min heap, or the node with the largest key, if this is a max heap.

extract

public java.lang.Object extract()

Extracts the extreme element of the heap (either the minimum or the maximum, depending on weather this is a min heap or a max heap).

Returns:

the object associated with the node with the extreme key.

See Also:

removeExtreme()

removeExtreme

public FibonacciHeap.Node removeExtreme()

Removes the smallest element from the heap if this is a min heap, or the largest element if this is a max heap. This will cause the trees in the heap to be consolidated, if necessary.

Running time: O(log n) amortized

Returns:

node with the extreme 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 FibonacciHeap union(FibonacciHeap h1,
                                  FibonacciHeap 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

Throws:

java.lang.IllegalArgumentException - Thrown if h1 and h2 are not the same type of heap (i.e. if one is a min-heap and the other is a max-heap).

toString

public java.lang.String toString()

Creates a String representation of this Fibonacci heap.

Returns:

String of this.

cascadingCut

protected void cascadingCut(FibonacciHeap.Node 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(FibonacciHeap.Node x,
                   FibonacciHeap.Node 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(FibonacciHeap.Node y,
                    FibonacciHeap.Node 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