net.cscott.jutil
Heaps support create, insert, minimum, extract-min,
union, decrease-key, and delete operations. There are three primary
implementations, each with different expected run-times:| Procedure | BinaryHeap(worst-case) |
BinomialHeap(worst-case) |
FibonacciHeap(amortized) |
|---|---|---|---|
| MAKE-HEAP | Theta(1) | Theta(1) | Theta(1) |
| INSERT | Theta(lg n) | O(lg n) | Theta(1) |
| MINIMUM | Theta(1) | O(lg n) | Theta(1) |
| EXTRACT-MIN | Theta(lg n) | Theta(lg n) | O(lg n) |
| UNION | Theta(n) | O(lg n) | Theta(1) |
| DECREASE-KEY | Theta(lg n) | Theta(lg n) | Theta(1) |
| UPDATE-KEY | Theta(lg n) | Theta(lg n) | Theta(lg n) |
| DELETE | Theta(lg n) | Theta(lg n) | O(lg n) |
All implementations of Heap should have a no-argument
constructor which implements the
MAKE-HEAP operation in
the above-stated time bound. In addition, certain implementations
may also have constructors which take a Map or
Heap and construct a heap in less time than it would
take to call insert() on each item on an initially-empty
Heap.
Note that the
UPDATE-KEY operation is
typically implemented as a delete followed by an insert, which
often has worse performance than a
DECREASE-KEY operation.
However, some algorithms need to increase keys as well as decrease
them; there's nothing you can do about that.
Version: $Id: Heap.java,v 1.2 2004/01/13 20:47:05 cananian Exp $
See Also: BinaryHeap BinomialHeap FibonacciHeap
| Method Summary | |
|---|---|
| void | clear() Removes all entries from this Heap. |
| Comparator<K> | comparator() Returns the comparator associated with this Heap,
or null if it uses its elements' natural ordering. |
| 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() Returns a collection view of all the Map.Entrys
in this Heap. |
| boolean | equals(Object o) Compares the specified object with this heap for equality.
|
| Entry<K,V> | extractMinimum() Remove and return a map entry with minimal key. |
| int | hashCode() Returns the hash code for this heap. |
| Entry<K,V> | insert(K key, V value) Inserts a node with the specified key and value into the
Heap. |
| boolean | isEmpty() Returns true if this Heap has no more
entries. |
| Entry<K,V> | minimum() Returns a mapping entry with minimal key. |
| int | size() Returns the number of entries in this Heap. |
| String | toString() Returns a string representation of this Heap. |
| void | union(Heap<? extends K,? extends V> h) Merges all of the mappings from the specified Heap
into this Heap. |
| void | updateKey(Entry<K,V> me, K newkey) Replace the key in the specified map entry with the specified key,
which may be either larger or smaller than its current key. |
Heap.Heap,
or null if it uses its elements' natural ordering.Map.Entrys
in this Heap.true iff the given object is also a
Heap and the Collections returned
by their entries() methods are equal using
the equals() method of Collection.Throws: java.util.NoSuchElementException if the heap has no entries.
Collection returned by entries().Heap. Returns the generated Map.Entry
which may be stored and eventually passed back to
decreaseKey() or delete to remove
this node.true if this Heap has no more
entries.Throws: java.util.NoSuchElementException if the heap has no entries.
Heap.Heap.Heap
into this Heap. Note that duplicates are
permitted. After calling union(), the Heap
passed in as an argument will be empty.
Note that usually efficient implementations of this method require
that the Heap argument be from the same implementation
as this. (That is, they must both be binomial heaps, or
both fibonacci heaps, etc.)