net.cscott.jutil

Interface Heap<K,V>

All Known Implementing Classes:

AbstractHeap, BinaryHeap, BinomialHeap, FibonacciHeap

public interface Heap<K,V>

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

See Also:

BinaryHeap, BinomialHeap, FibonacciHeap

Method Summary

Modifier and Type	Method and Description
void	clear() Removes all entries from this Heap.
java.util.Comparator<K>	comparator() Returns the comparator associated with this Heap, or null if it uses its elements' natural ordering.
void	decreaseKey(java.util.Map.Entry<K,V> me, K newkey) Replace the key in the specified map entry with the specified smaller key.
void	delete(java.util.Map.Entry<K,V> me) Remove the specified map entry from the mapping.
java.util.Collection<java.util.Map.Entry<K,V>>	entries() Returns a collection view of all the Map.Entrys in this Heap.
boolean	equals(java.lang.Object o) Compares the specified object with this heap for equality.
java.util.Map.Entry<K,V>	extractMinimum() Remove and return a map entry with minimal key.
int	hashCode() Returns the hash code for this heap.
java.util.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.
java.util.Map.Entry<K,V>	minimum() Returns a mapping entry with minimal key.
int	size() Returns the number of entries in this Heap.
java.lang.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(java.util.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

insert

java.util.Map.Entry<K,V> insert(K key,
                                V value)

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

minimum

java.util.Map.Entry<K,V> minimum()

Returns a mapping entry with minimal key.

Throws:

java.util.NoSuchElementException - if the heap has no entries.

extractMinimum

java.util.Map.Entry<K,V> extractMinimum()

Remove and return a map entry with minimal key.

Throws:

java.util.NoSuchElementException - if the heap has no entries.

union

void union(Heap<? extends K,? extends V> h)

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

decreaseKey

void decreaseKey(java.util.Map.Entry<K,V> me,
                 K newkey)

Replace the key in the specified map entry with the specified smaller key.

updateKey

void updateKey(java.util.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.

delete

void delete(java.util.Map.Entry<K,V> me)

Remove the specified map entry from the mapping.

isEmpty

boolean isEmpty()

Returns true if this Heap has no more entries.

clear

void clear()

Removes all entries from this Heap.

size

int size()

Returns the number of entries in this Heap.

entries

java.util.Collection<java.util.Map.Entry<K,V>> entries()

Returns a collection view of all the Map.Entrys in this Heap.

hashCode

int hashCode()

Returns the hash code for this heap. The hash code for this heap will be one greater than the hash code for the Collection returned by entries().

Overrides:

hashCode in class java.lang.Object

equals

boolean equals(java.lang.Object o)

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.

Overrides:

equals in class java.lang.Object

toString

java.lang.String toString()

Returns a string representation of this Heap.

Overrides:

toString in class java.lang.Object

comparator

java.util.Comparator<K> comparator()

Returns the comparator associated with this Heap, or null if it uses its elements' natural ordering.