
JUtil  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
public interface Heap<K,V>
Heap
s support create, insert, minimum, extractmin,
union, decreasekey, and delete operations. There are three primary
implementations, each with different expected runtimes:
Procedure  BinaryHeap (worstcase) 
BinomialHeap (worstcase) 
FibonacciHeap (amortized) 

MAKEHEAP  Theta(1)  Theta(1)  Theta(1) 
INSERT  Theta(lg n)  O(lg n)  Theta(1) 
MINIMUM  Theta(1)  O(lg n)  Theta(1) 
EXTRACTMIN  Theta(lg n)  Theta(lg n)  O(lg n) 
UNION  Theta(n)  O(lg n)  Theta(1) 
DECREASEKEY  Theta(lg n)  Theta(lg n)  Theta(1) 
UPDATEKEY  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 noargument
constructor which implements the
MAKEHEAP operation in
the abovestated 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 initiallyempty
Heap
.
Note that the
UPDATEKEY operation is
typically implemented as a delete followed by an insert, which
often has worse performance than a
DECREASEKEY operation.
However, some algorithms need to increase keys as well as decrease
them; there's nothing you can do about that.
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(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()
Returns a collection view of all the Map.Entry s
in this Heap . 
boolean 
equals(Object o)
Compares the specified object with this heap for equality. 
Map.Entry<K,V> 
extractMinimum()
Remove and return a map entry with minimal key. 
int 
hashCode()
Returns the hash code for this heap. 
Map.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. 
Map.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(Map.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. 
Method Detail 

Map.Entry<K,V> insert(K key, V value)
Heap
. Returns the generated Map.Entry
which may be stored and eventually passed back to
decreaseKey()
or delete
to remove
this node.
Map.Entry<K,V> minimum()
NoSuchElementException
 if the heap has no entries.Map.Entry<K,V> extractMinimum()
NoSuchElementException
 if the heap has no entries.void union(Heap<? extends K,? extends V> h)
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.)
void decreaseKey(Map.Entry<K,V> me, K newkey)
void updateKey(Map.Entry<K,V> me, K newkey)
void delete(Map.Entry<K,V> me)
boolean isEmpty()
true
if this Heap
has no more
entries.
void clear()
Heap
.
int size()
Heap
.
Collection<Map.Entry<K,V>> entries()
Map.Entry
s
in this Heap
.
int hashCode()
Collection
returned by entries()
.
hashCode
in class Object
boolean equals(Object o)
true
iff the given object is also a
Heap
and the Collection
s returned
by their entries()
methods are equal using
the equals()
method of Collection
.
equals
in class Object
String toString()
Heap
.
toString
in class Object
Comparator<K> comparator()
Heap
,
or null
if it uses its elements' natural ordering.

JUtil  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 