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.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(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
java.util.Map.Entrys 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 java.util.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. |
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.
public BinomialHeap(Comparator<
K> c)
Constructs a new, empty
BinomialHeap, sorted according
to the given comparator. O(1) time.
public BinomialHeap(
Heap<
K,? extends
V> h)
Constructs a new binomial heap with the same entries as the specified
Heap. O(n) time.
public BinomialHeap(Collection<? extends Entry<? extends
K,? extends
V>> collection, Comparator<
K> comparator)
Constructs a binomial heap from a collection of
java.util.Map.Entrys and a key comparator. O(n) time.
public void clear()
Removes all mappings from this map. O(1) time.
Creates a new BinomialHeap with all the key-value pairs this one
has. O(n) time.
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.
public void delete(Entry<
K,
V> me)
Remove the specified map entry from the mapping. O(lg n) time.
public Collection<Entry<
K,
V>> entries()
Return an unmodifiable collection of entries in this heap.
public Entry<
K,
V> extractMinimum()
Remove and return the map entry with minimal key. O(lg n) time.
public Entry<
K,
V> find(
K key)
Lookup a java.util.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.
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 java.util.Map.Entry added.
protected void insert(Entry<
K,
V> me)
public boolean isEmpty()
Returns true
if this map contains no key-value mappings.
public static void main(String[] argv)
Self-test function.
public Entry<
K,
V> minimum()
Returns a mapping entry with minimal key. Takes O(lg n) time.
protected final
K setKey(Entry<
K,
V> me,
K newkey)
public int size()
Returns the size of this map. O(lg n) time.
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.
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.
Copyright (c) 2006 C. Scott Ananian