Heap<K,V> (JUtil documentation)

Heaps support create, insert, minimum, extract-min, union, decrease-key, and delete operations. There are three primary implementations, each with different expected run-times:

Running times for operations on three implementations of mergable heaps. The number of items in the heap(s) at the time of an operation is denoted by n.

*(From "Introduction to Algorithms" by Cormen, Leiserson, and Rivest)*
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 $

Author: C. Scott Ananian

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

Compares the specified object with this heap for equality. Returns 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.

extractMinimum

hashCode

insert

Inserts a node with the specified key and value into the Heap. Returns the generated java.util.Map.Entry which may be stored and eventually passed back to decreaseKey() or delete to remove this node.

Merges all of the mappings from the specified 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.)

Interface Heap<K,V>