net.cscott.jutil

Class BinomialHeap<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.4 2004/01/13 21:40:19 cananian Exp $

Author: C. Scott Ananian

Constructor Summary
	BinomialHeap() Constructs a new, empty `BinomialHeap`, sorted according to the keys' natural order.
	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`.
	BinomialHeap(Collection<? extends Entry<? extends K,? extends V>> collection, Comparator<K> comparator) Constructs a binomial heap from a collection of `Map.Entry`s and a key comparator.

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(Entry<K,V> me, K newkey) Replace the key in the specified map entry with the specified smaller key.
void	delete(Entry<K,V> me) Remove the specified map entry from the mapping.
Collection<Entry<K,V>>	entries() Return an unmodifiable collection of entries in this heap.
Entry<K,V>	extractMinimum() Remove and return the map entry with minimal key.
Entry<K,V>	find(K key) Lookup a `Map.Entry` in the heap with key equal to the specified key.
Entry<K,V>	insert(K key, V value) Associates the specified value with the specified key in the map.
protected void	insert(Entry<K,V> me)
boolean	isEmpty() Returns `true` if this map contains no key-value mappings.
static void	main(String[] argv) Self-test function.
Entry<K,V>	minimum() Returns a mapping entry with minimal key.
protected K	setKey(Entry<K,V> me, K newkey)
int	size() Returns the size of this map.
void	union(Heap<? extends K,? extends V> h) Add all the entries from the given heap to this one.
void	union(BinomialHeap<K,V> m) Merges all of the mappings from the specified map to this map.

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 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

clear

public void clear()

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

clone

public BinomialHeap<K,V> clone()

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

decreaseKey

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

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

delete

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

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

entries

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

Return an unmodifiable collection of entries in this heap.

extractMinimum

public Entry<K,V> extractMinimum()

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

find

public 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.

insert

public 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.

Returns: The Map.Entry added.

insert

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

isEmpty

public boolean isEmpty()

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

main

public static void main(String[] argv)

Self-test function.

minimum

public Entry<K,V> minimum()

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

setKey

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

size

public int size()

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

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.

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.