BinaryHeap (JUtil documentation)

Package

Class

Use

Tree

Deprecated

Index

Help

JUtil

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

net.cscott.jutil
Class BinaryHeap<K,V>

java.lang.Object
  net.cscott.jutil.AbstractHeap<K,V>
      net.cscott.jutil.BinaryHeap<K,V>

All Implemented Interfaces:: Heap<K,V>

public final class BinaryHeap<K,V>
extends AbstractHeap<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(int) (for what CLR calls 'heapify') and upheap(int) (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(Collection<? extends Map.Entry<? extends K,? extends V>> collection, Comparator<K> comparator)` Builds a binary heap from a collection of `Map.Entry`s and a key comparator.
`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.

Method Summary
`void`	`clear()` Removes all entries from this `Heap`.
`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`.
`Map.Entry<K,V>`	`extractMinimum()` Remove and return a map entry with minimal key.
`Map.Entry<K,V>`	`insert(K key, V value)` Inserts a node with the specified key and value into the `Heap`.
`static void`	`main(String[] args)` Self-test function.
`Map.Entry<K,V>`	`minimum()` Returns a mapping entry with minimal key.
`protected K`	`setKey(Map.Entry<K,V> me, K newkey)` This method should set the key for the specified `Map.Entry` to the given `newkey`.
`int`	`size()` Returns the number of entries in 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.

Methods inherited from class net.cscott.jutil.AbstractHeap
`comparator, entryComparator, equals, hashCode, insert, isEmpty, keyComparator, toString`

Methods inherited from class java.lang.Object
`clone, finalize, getClass, notify, notifyAll, wait, wait, wait`

Constructor Detail

BinaryHeap

public BinaryHeap()

Creates a new, empty BinaryHeap, which will use the keys' natural order.

BinaryHeap

public BinaryHeap(Comparator<K> c)

Creates a new, empty BinaryHeap with the specified comparator.

BinaryHeap

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.

BinaryHeap

public BinaryHeap(Collection<? extends Map.Entry<? extends K,? extends V>> collection,
                  Comparator<K> comparator)

Builds a binary heap from a collection of Map.Entrys and a key comparator. O(n) time.

Method Detail