net.cscott.jutil
Class BinomialHeap<K,V>

java.lang.Object
  net.cscott.jutil.AbstractHeap<K,V>
      net.cscott.jutil.BinomialHeap<K,V>

All Implemented Interfaces:

Cloneable, Heap<K,V>

public class BinomialHeap<K,V>
extends AbstractHeap<K,V>
implements Cloneable

A BinomialHeap allows O(lg n) time bounds for insert, minimum, extract-min, union, decrease-key, and delete operations. Implementation is based on the description in Introduction to Algorithms by Cormen, Leiserson, and Rivest, on page 400 and following.

Version:

$Id: BinomialHeap.java,v 1.8 2006-10-30 19:58:05 cananian Exp $

Author:

C. Scott Ananian

Constructor Summary

BinomialHeap()
Constructs a new, empty BinomialHeap, sorted according to the keys' natural order.

BinomialHeap(Collection<? extends Map.Entry<? extends K,? extends V>> collection, Comparator<K> comparator)
Constructs a binomial heap from a collection of Map.Entrys and a key comparator.

BinomialHeap(Comparator<K> c)
Constructs a new, empty BinomialHeap, sorted according to the given comparator.

BinomialHeap(Heap<K,? extends V> h)
Constructs a new binomial heap with the same entries as the specified Heap.

Method Summary

void	clear() Removes all mappings from this map.
BinomialHeap<K,V>	clone() Creates a new BinomialHeap with all the key-value pairs this one has.
void	decreaseKey(Map.Entry<K,V> me, K newkey) Replace the key in the specified map entry with the specified smaller key.
void	delete(Map.Entry<K,V> me) Remove the specified map entry from the mapping.
Collection<Map.Entry<K,V>>	entries() Return an unmodifiable collection of entries in this heap.
Map.Entry<K,V>	extractMinimum() Remove and return the map entry with minimal key.
Map.Entry<K,V>	find(K key) Lookup a Map.Entry in the heap with key equal to the specified key.
Map.Entry<K,V>	insert(K key, V value) Associates the specified value with the specified key in the map.
protected void	insert(Map.Entry<K,V> me) This method should insert the specified Map.Entry, which is not currently in the Heap, into the Heap.
boolean	isEmpty() Returns true if this map contains no key-value mappings.
static void	main(String[] argv) Self-test function.
Map.Entry<K,V>	minimum() Returns a mapping entry with minimal key.
protected K	setKey(Map.Entry<K,V> me, K newkey) This method should set the key for the specified Map.Entry to the given newkey.
int	size() Returns the size of this map.
void	union(BinomialHeap<K,V> m) Merges all of the mappings from the specified map to this map.
void	union(Heap<? extends K,? extends V> h) Add all the entries from the given heap to this one.

Methods inherited from class net.cscott.jutil.AbstractHeap

comparator, entryComparator, equals, hashCode, keyComparator, toString, updateKey

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

BinomialHeap

public BinomialHeap()

Constructs a new, empty BinomialHeap, sorted according to the keys' natural order. All keys inserted into the new map must implement the Comparable interface. O(1) time.

BinomialHeap

public BinomialHeap(Comparator<K> c)

Constructs a new, empty BinomialHeap, sorted according to the given comparator. O(1) time.

BinomialHeap

public BinomialHeap(Heap<K,? extends V> h)

Constructs a new binomial heap with the same entries as the specified Heap. O(n) time.

BinomialHeap

public BinomialHeap(Collection<? extends Map.Entry<? extends K,? extends V>> collection,
                    Comparator<K> comparator)

Constructs a binomial heap from a collection of Map.Entrys and a key comparator. O(n) time.

Method Detail

minimum

public Map.Entry<K,V> minimum()

Returns a mapping entry with minimal key. Takes O(lg n) time.

Specified by:

minimum in interface Heap<K,V>

Specified by:

minimum in class AbstractHeap<K,V>

union

public void union(Heap<? extends K,? extends V> h)

Add all the entries from the given heap to this one. The given heap will be empty on return. Takes O(lg n) time if the given heap is a BinomialHeap and its entry comparator is the same as this one's. Otherwise, it takes O(n) time.

Specified by:

union in interface Heap<K,V>

Overrides:

union in class AbstractHeap<K,V>

union

public void union(BinomialHeap<K,V> m)

Merges all of the mappings from the specified map to this map. Note that duplicates are permitted. This operation takes O(lg n), where n is the number of entries in the resulting map. The comparator for m must be identical to the comparator for this. After calling union(), the specified map will be empty.

insert

public Map.Entry<K,V> insert(K key,
                             V value)

Associates the specified value with the specified key in the map. If the map previously contained a mapping for this key, the old value is not replaced; both mappings will be present after the insert(). O(lg n) time.

Specified by:

insert in interface Heap<K,V>

Specified by:

insert in class AbstractHeap<K,V>

Returns:

The Map.Entry added.

insert

protected void insert(Map.Entry<K,V> me)

Description copied from class: AbstractHeap

This method should insert the specified Map.Entry, which is not currently in the Heap, into the Heap. Implementation is optional, but it is required if you use the default implementation of updateKey().

Overrides:

insert in class AbstractHeap<K,V>

extractMinimum

public Map.Entry<K,V> extractMinimum()

Remove and return the map entry with minimal key. O(lg n) time.

Specified by:

extractMinimum in interface Heap<K,V>

Overrides:

extractMinimum in class AbstractHeap<K,V>

decreaseKey

public void decreaseKey(Map.Entry<K,V> me,
                        K newkey)

Replace the key in the specified map entry with the specified smaller key. O(lg n) time.

Specified by:

decreaseKey in interface Heap<K,V>

Specified by:

decreaseKey in class AbstractHeap<K,V>

delete

public void delete(Map.Entry<K,V> me)

Remove the specified map entry from the mapping. O(lg n) time.

Specified by:

delete in interface Heap<K,V>

Specified by:

delete in class AbstractHeap<K,V>

entries

public Collection<Map.Entry<K,V>> entries()

Return an unmodifiable collection of entries in this heap.

Specified by:

entries in interface Heap<K,V>

Specified by:

entries in class AbstractHeap<K,V>

size

public int size()

Returns the size of this map. O(lg n) time.

Specified by:

size in interface Heap<K,V>

Specified by:

size in class AbstractHeap<K,V>

clear

public void clear()

Removes all mappings from this map. O(1) time.

Specified by:

clear in interface Heap<K,V>

Specified by:

clear in class AbstractHeap<K,V>

isEmpty

public boolean isEmpty()

Returns true if this map contains no key-value mappings.

Specified by:

isEmpty in interface Heap<K,V>

Overrides:

isEmpty in class AbstractHeap<K,V>

clone

public BinomialHeap<K,V> clone()

Creates a new BinomialHeap with all the key-value pairs this one has. O(n) time.

Overrides:

clone in class Object

find

public Map.Entry<K,V> find(K key)

Lookup a Map.Entry in the heap with key equal to the specified key. O(n), although pruning is done on subtrees with root larger than the specified key. What this means is that the smaller the key is, the faster this will run.

setKey

protected final K setKey(Map.Entry<K,V> me,
                         K newkey)

Description copied from class: AbstractHeap

This method should set the key for the specified Map.Entry to the given newkey. Implementation is optional, but it is required if you use the default implementation of updateKey().

Overrides:

setKey in class AbstractHeap<K,V>

main

public static void main(String[] argv)

Self-test function.