com.mhhe.clrs2e
Class BinomialHeap

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

public class BinomialHeap

extends MergeableHeap

Implementation of a binomial heap from Chapter 19 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class	BinomialHeap.Handle Inner class for the handle given back to the caller upon an insertion.
private static class	BinomialHeap.Node Inner class for a node within a binomial heap.

Field Summary

private BinomialHeap.Node

head The head of the singly linked root list.

Constructor Summary

BinomialHeap()
Creates an empty binomial heap.

Method Summary

private static BinomialHeap.Node	binomialHeapMerge(com.mhhe.clrs2e.BinomialHeap h1, com.mhhe.clrs2e.BinomialHeap h2) Merges the root lists of two binomial heaps together into a single root list.
private void	binomialLink(BinomialHeap.Node y, BinomialHeap.Node z) Links one binomial tree to another.
BinomialHeap.Node	bubbleUp(BinomialHeap.Node x, boolean toRoot) Bubbles the value in node up in the binomial heap.
void	decreaseKey(java.lang.Object handle, java.lang.Comparable k) Decreases the key of a node.
void	delete(java.lang.Object handle) 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 binomial heap.
java.lang.Object	insert(com.mhhe.clrs2e.DynamicSetElement e) Inserts a dynamic set element into the binomial heap.
com.mhhe.clrs2e.DynamicSetElement	minimum() Returns the object whose key is minimum.
private void	removeFromRootList(BinomialHeap.Node x, BinomialHeap.Node pred) Helper method to remove a node from the root list.
java.lang.String	toString() Returns the String representation of this binomial heap, based on the objects in the nodes.
com.mhhe.clrs2e.MergeableHeap	union(com.mhhe.clrs2e.MergeableHeap h2) Creates a new binomial heap that contains all the elements of two binomial heaps.

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

head

private BinomialHeap.Node head

The head of the singly linked root list.

Constructor Detail

BinomialHeap

public BinomialHeap()

Creates an empty binomial heap.

Method Detail

toString

public java.lang.String toString()

Returns the String representation of this binomial 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 binomial heap.

Specified by:

insert in class MergeableHeap

Parameters:

e - The dynamic set element to be inserted.

Returns:

A handle to the inserted item.

minimum

public com.mhhe.clrs2e.DynamicSetElement minimum()

Returns the object whose key is minimum. Implements the Binomial-Heap-Minimum procedure on page 462.

Specified by:

minimum in class MergeableHeap

extractMin

public com.mhhe.clrs2e.DynamicSetElement extractMin()

Removes and returns the smallest object in the binomial heap.

Specified by:

extractMin in class MergeableHeap

removeFromRootList

private void removeFromRootList(BinomialHeap.Node x,
                                BinomialHeap.Node pred)

Helper method to remove a node from the root list.

Parameters:

x - The node to remove from the root list.

pred - The predecessor of x in the root list, or null if x is the first node in the root list.

union

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

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

Implements the Binomial-Heap-Union procedure on page 463, with h1 being this object.

Specified by:

union in class MergeableHeap

Parameters:

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

Returns:

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

binomialLink

private void binomialLink(BinomialHeap.Node y,
                          BinomialHeap.Node z)

Links one binomial tree to another.

Parameters:

y - The root of one binomial tree.

z - The root of another binomial tree; this root becomes the parent of y.

binomialHeapMerge

private static BinomialHeap.Node binomialHeapMerge(com.mhhe.clrs2e.BinomialHeap h1,
                                                   com.mhhe.clrs2e.BinomialHeap h2)

Merges the root lists of two binomial heaps together into a single root list. The degrees in the merged root list appear in monotonically increasing order.

Parameters:

h1 - One binomial heap.

h2 - The other binomial heap.

Returns:

The head of the merged list.

decreaseKey

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

Decreases the key of a node. Implements the Binomial-Heap-Decrease-Key procedure on page 470.

Parameters:

handle - Handle to the node whose key is to be decreased.

k - The new key.

Throws:

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

bubbleUp

public BinomialHeap.Node bubbleUp(BinomialHeap.Node x,
                                  boolean toRoot)

Bubbles the value in node up in the binomial heap. Because this procedure moves objects around within nodes, it has to update handles, too, so that the caller's idea of where a handle points is still accurate.

Parameters:

x - The node whose value is to be bubbled up.

toRoot - If true, the value is bubbled all the way to the root. If false, the value bubbles up until its key is less than or equal to its parent's key, or until it becomes the root.

Returns:

A reference to the node in which the value originally in x ends up.

delete

public void delete(java.lang.Object handle)

Deletes a node. Because we do not have a negative infinity in the Comparable interface, we indirectly emulate the action of the Binomial-Heap-Delete procedure on page 470.

Parameters:

handle - Handle to 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 - Handle to the node.

Throws:

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