net.cscott.jutil

Class BinaryHeap<K,V>

public final class BinaryHeap<K,V> extends AbstractHeap<K,V>

BinaryHeap is an implementation of a binary heap. The implementation in CLR is followed, except the comparisons are reversed to keep the minimum element on the top of the heap. In addition, the function names downheap() (for what CLR calls 'heapify') and upheap() (which is part of the INSERT operation) have been adopted from Sedgewick's book.

Version: $Id: BinaryHeap.java,v 1.3 2004/01/13 21:40:19 cananian Exp $

Author: C. Scott Ananian

See Also: Heap

Constructor Summary
	BinaryHeap() Creates a new, empty `BinaryHeap`, which will use the keys' natural order.
	BinaryHeap(Comparator<K> c) Creates a new, empty `BinaryHeap` with the specified comparator.
	BinaryHeap(Heap<K,? extends V> h) Builds a binary heap from the given heap, using the same key comparator as the given heap.
	BinaryHeap(Collection<? extends Entry<? extends K,? extends V>> collection, Comparator<K> comparator) Builds a binary heap from a collection of `Map.Entry`s and a key comparator.

Method Summary
void	clear()
void	decreaseKey(Entry<K,V> me, K newkey)
void	delete(Entry<K,V> me)
Collection<Entry<K,V>>	entries()
Entry<K,V>	extractMinimum()
Entry<K,V>	insert(K key, V value)
static void	main(String[] args) Self-test function.
Entry<K,V>	minimum()
protected K	setKey(Entry<K,V> me, K newkey)
int	size()
void	union(Heap<? extends K,? extends V> h)
void	updateKey(Entry<K,V> me, K newkey)