com.mhhe.clrs2e
Class FibHeap

java.lang.Object
  |
  +--com.mhhe.clrs2e.MergeableHeap
        |
        +--com.mhhe.clrs2e.FibHeap

public class FibHeap

extends MergeableHeap

Implementation of a Fibonacci heap from Chapter 20 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class

FibHeap.Node Inner class for a node within a Fibonaaci heap.

Field Summary

private FibHeap.Node	min The node in root list with the minimum key.
(package private) int	n How many nodes are in this Fibonacci heap.

Constructor Summary

FibHeap()
Creates an empty Fibonacci heap.

Method Summary

java.lang.Object	addChild(java.lang.Object node, com.mhhe.clrs2e.DynamicSetElement e, boolean marked) Adds a child with a dynamic set element to a node, inserting the child into the Fibonacci heap.
private void	cascadingCut(FibHeap.Node y) Performs a cascading cut operation.
private int	computeD() Returns D(n) = floor(log base phi of n), where phi = (1 + sqrt(5)) / 2.
private void	consolidate() Consolidates the root list of this Fibonacci heap.
private void	cut(FibHeap.Node x, FibHeap.Node y) Cuts the link between a node and its parent.
void	decreaseKey(java.lang.Object node, java.lang.Comparable k) Decreases the key of a node.
void	delete(java.lang.Object node) Deletes a node.
java.lang.String	dereference(java.lang.Object handle) Returns the String representation of a node's object.
com.mhhe.clrs2e.DynamicSetElement	extractMin() Removes and returns the smallest object in the Fibonacci heap.
private void	fibHeapLink(FibHeap.Node y, FibHeap.Node x) Links one root to another.
java.lang.Object	insert(com.mhhe.clrs2e.DynamicSetElement e) Inserts a dynamic set element into the Fibonacci heap.
void	mark(java.lang.Object node) Marks a node.
com.mhhe.clrs2e.DynamicSetElement	minimum() Returns the object whose key is minimum.
private FibHeap.Node	spliceIn(FibHeap.Node x, FibHeap.Node y) Splices the node list containing one node into the node list containing another node, just to the left of it.
java.lang.String	toString() Returns the String representation of this Fibonacci heap, based on the objects in the nodes.
com.mhhe.clrs2e.MergeableHeap	union(com.mhhe.clrs2e.MergeableHeap h2) Creates a new Fibonacci heap that contains all the elements of two Fibonacci heaps.
private void	updateForDecreaseKey(FibHeap.Node x, boolean delete) Changes the structure of the Fibonacci heap as part of a decreaseKey operation.

Methods inherited from class com.mhhe.clrs2e.MergeableHeap

union

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

min

private FibHeap.Node min

The node in root list with the minimum key.

n

int n

How many nodes are in this Fibonacci heap.

Constructor Detail

FibHeap

public FibHeap()

Creates an empty Fibonacci heap.

Method Detail

toString

public java.lang.String toString()

Returns the String representation of this Fibonacci heap, based on the objects in the nodes. It represents the depth of each node by two spaces per depth preceding the String representation of the node.

Overrides:

toString in class java.lang.Object

insert

public java.lang.Object insert(com.mhhe.clrs2e.DynamicSetElement e)

Inserts a dynamic set element into the Fibonacci heap. Implements the Fib-Heap-Insert procedure on page 480.

Specified by:

insert in class MergeableHeap

Parameters:

e - The dynamic set element to be inserted.

Returns:

A handle to the inserted item.

spliceIn

private FibHeap.Node spliceIn(FibHeap.Node x,
                              FibHeap.Node y)

Splices the node list containing one node into the node list containing another node, just to the left of it.

Parameters:

x - The node whose list is to be spliced into the other.

y - The node whose list is to be spliced into.

Returns:

If x is null, then x's list is empty, and we just return y. If y is null, then y's list is empty and we just return x. If neither x nor y is null, we return x as a pointer into the list.

minimum

public com.mhhe.clrs2e.DynamicSetElement minimum()

Returns the object whose key is minimum.

Specified by:

minimum in class MergeableHeap

extractMin

public com.mhhe.clrs2e.DynamicSetElement extractMin()

Removes and returns the smallest object in the Fibonacci heap. Implements the Fib-Heap-Extract-Min procedure on page 483.

Specified by:

extractMin in class MergeableHeap

consolidate

private void consolidate()

Consolidates the root list of this Fibonacci heap. Implements the Consolidate procedure on page 486.

fibHeapLink

private void fibHeapLink(FibHeap.Node y,
                         FibHeap.Node x)

Links one root to another. Implements the Fib-Heap-Link procedure on page 486.

Parameters:

y - The root to be linked to x.

x - The root that y is linked to.

computeD

private int computeD()

Returns D(n) = floor(log base phi of n), where phi = (1 + sqrt(5)) / 2. Assumes that n > 0.

union

public com.mhhe.clrs2e.MergeableHeap union(com.mhhe.clrs2e.MergeableHeap h2)

Creates a new Fibonacci heap that contains all the elements of two Fibonacci heaps. One of the original Fibonacci heaps is the object on which this method is called; the other is specified by the parameter. The two original Fibonacci heaps should no longer be used after this operation.

Implements the Fib-Heap-Union procedure on page 482, with h1 being this object.

Specified by:

union in class MergeableHeap

Parameters:

h2 - The Fibonacci heap to be merged with this one.

Returns:

The new Fibonacci heap that contains all the elements of this Fibonacci heap and h2.

decreaseKey

public void decreaseKey(java.lang.Object node,
                        java.lang.Comparable k)
                 throws KeyUpdateException

Decreases the key of a node. Implements the Fib-Heap-Decrease-Key procedure on page 489.

Parameters:

node - The node whose key is to be decreased.

k - The new key.

Throws:

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

updateForDecreaseKey

private void updateForDecreaseKey(FibHeap.Node x,
                                  boolean delete)

Changes the structure of the Fibonacci heap as part of a decreaseKey operation.

Parameters:

x - The node whose key is being decreased.

delete - If true, ignore x's key and treat it as though it were negative infinity, because we're decreasing the key as part of a delete operation.

cut

private void cut(FibHeap.Node x,
                 FibHeap.Node y)

Cuts the link between a node and its parent. Implements the Cut procedure on page 489.

Parameters:

x - The node.

y - x's parent.

cascadingCut

private void cascadingCut(FibHeap.Node y)

Performs a cascading cut operation. Implements the Cascading-Cut procedure on page 490.

Parameters:

y - The node being cut.

delete

public void delete(java.lang.Object node)

Deletes a node. Implements the Fib-Heap-Delete procedure on page 492.

Parameters:

node - The node to be deleted.

dereference

public java.lang.String dereference(java.lang.Object handle)

Returns the String representation of a node's object.

Parameters:

handle - The node.

Throws:

java.lang.ClassCastException - if handle is not a reference to a node object.

addChild

public java.lang.Object addChild(java.lang.Object node,
                                 com.mhhe.clrs2e.DynamicSetElement e,
                                 boolean marked)

Adds a child with a dynamic set element to a node, inserting the child into the Fibonacci heap. We use this method just so we can create examples exactly like those in the text.

Parameters:

node - The node to which the child is added.

e - The dynamic set element to appear in the new node.

marked - true if the new node is to be marked, false otherwise.

Returns:

A handle to the inserted item.

mark

public void mark(java.lang.Object node)

Marks a node. We use this method just so we can create examples exactly like those in the text.

Parameters:

node - The node to be marked.