net.cscott.jutil
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.4 2006-10-30 20:14:41 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 java.util.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) |
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. |
null
if it uses its elements' natural ordering.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.
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.
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.)