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
BinaryHeap
(for what CLR calls 'heapify') and
BinaryHeap (which
is part of the INSERT operation) have been adopted from
Sedgewick's book.
Version: $Id: BinaryHeap.java,v 1.7 2006-10-30 20:14:41 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 java.util.Map.Entrys
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) |
public BinaryHeap()
Creates a new, empty
BinaryHeap, which will
use the keys' natural order.
public BinaryHeap(Comparator<
K> c)
Creates a new, empty
BinaryHeap with the
specified comparator.
public BinaryHeap(
Heap<
K,? extends
V> h)
Builds a binary heap from the given heap, using
the same key comparator as the given heap. O(n) time.
public BinaryHeap(Collection<? extends Entry<? extends
K,? extends
V>> collection, Comparator<
K> comparator)
Builds a binary heap from a collection of java.util.Map.Entrys
and a key comparator.
O(n) time.
public void clear()
public void decreaseKey(Entry<
K,
V> me,
K newkey)
public void delete(Entry<
K,
V> me)
public Collection<Entry<
K,
V>> entries()
public Entry<
K,
V> extractMinimum()
public Entry<
K,
V> insert(
K key,
V value)
public static void main(String[] args)
Self-test function.
public Entry<
K,
V> minimum()
protected final
K setKey(Entry<
K,
V> me,
K newkey)
public int size()
public void union(
Heap<? extends
K,? extends
V> h)
public void updateKey(Entry<
K,
V> me,
K newkey)
Copyright (c) 2006 C. Scott Ananian