com.mhhe.clrs2e
Class MergeableHeap

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

Direct Known Subclasses:

BinomialHeap, FibHeap

public abstract class MergeableHeap

extends java.lang.Object

Abstract class for mergeable heap data structures, defined on page 455 of Introduction to Algorithms, Second edition.

The constructor of any implementing class should create an empty mergeable heap.

Constructor Summary

MergeableHeap()

Method Summary

abstract com.mhhe.clrs2e.DynamicSetElement	extractMin() Removes and returns the smallest dynamic set element in the mergeable heap.
abstract java.lang.Object	insert(com.mhhe.clrs2e.DynamicSetElement x) Inserts a dynamic set element into the mergeable heap.
abstract com.mhhe.clrs2e.DynamicSetElement	minimum() Returns the dynamic set element whose key is minimum.
abstract com.mhhe.clrs2e.MergeableHeap	union(com.mhhe.clrs2e.MergeableHeap h2) Creates a new mergeable heap that contains all the elements of two mergeable heaps.
static com.mhhe.clrs2e.MergeableHeap	union(com.mhhe.clrs2e.MergeableHeap h1, com.mhhe.clrs2e.MergeableHeap h2) Creates a new mergeable heap that contains all the elements of two mergeable heaps.

Methods inherited from class java.lang.Object

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

Constructor Detail

MergeableHeap

public MergeableHeap()

Method Detail

insert

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

Inserts a dynamic set element into the mergeable heap.

Parameters:

x - The dynamic set element to be inserted.

Returns:

A handle to the inserted item.

minimum

public abstract com.mhhe.clrs2e.DynamicSetElement minimum()

Returns the dynamic set element whose key is minimum.

extractMin

public abstract com.mhhe.clrs2e.DynamicSetElement extractMin()

Removes and returns the smallest dynamic set element in the mergeable heap.

union

public static com.mhhe.clrs2e.MergeableHeap union(com.mhhe.clrs2e.MergeableHeap h1,
                                                  com.mhhe.clrs2e.MergeableHeap h2)

Creates a new mergeable heap that contains all the elements of two mergeable heaps. The two original mergeable heaps should no longer be used after this operation.

Parameters:

h1 - One of the mergeable heaps to be merged.

h2 - The other mergeable heap to be merged.

Returns:

The new mergeable heap that contains all the elements of h1 and h2.

union

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

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

Parameters:

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

Returns:

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