BinaryHeap (JUtil documentation)

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>
```
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

Constructors
Constructor and Description
`BinaryHeap()` Creates a new, empty `BinaryHeap`, which will use the keys' natural order.
`BinaryHeap(java.util.Collection<? extends java.util.Map.Entry<? extends K,? extends V>> collection, java.util.Comparator<K> comparator)` Builds a binary heap from a collection of `Map.Entry`s and a key comparator.
`BinaryHeap(java.util.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

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`clear()` Removes all entries from this `Heap`.
`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.Entry`s in this `Heap`.
`java.util.Map.Entry<K,V>`	`extractMinimum()` Remove and return a map entry with minimal key.
`java.util.Map.Entry<K,V>`	`insert(K key, V value)` Inserts a node with the specified key and value into the `Heap`.
`static void`	`main(java.lang.String[] args)` Self-test function.
`java.util.Map.Entry<K,V>`	`minimum()` Returns a mapping entry with minimal key.
`protected K`	`setKey(java.util.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(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.

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(java.util.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(java.util.Collection<? extends java.util.Map.Entry<? extends K,? extends V>> collection,
                  java.util.Comparator<K> comparator)
```
    Builds a binary heap from a collection of Map.Entrys and a key comparator. O(n) time.
- Method Detail
  - insert
```
public java.util.Map.Entry<K,V> insert(K key,
                                       V value)
```
    Description copied from interface: Heap
    
    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.
    
    Specified by:
    
    insert in interface Heap<K,V>
    
    Specified by:
    
    insert in class AbstractHeap<K,V>
  - minimum
```
public java.util.Map.Entry<K,V> minimum()
```
    Description copied from interface: Heap
    
    Returns a mapping entry with minimal key.
    
    Specified by:
    
    minimum in interface Heap<K,V>
    
    Specified by:
    
    minimum in class AbstractHeap<K,V>
  - extractMinimum
```
public java.util.Map.Entry<K,V> extractMinimum()
```
    Description copied from interface: Heap
    
    Remove and return a map entry with minimal key.
    
    Specified by:
    
    extractMinimum in interface Heap<K,V>
    
    Overrides:
    
    extractMinimum in class AbstractHeap<K,V>
  - union
```
public void union(Heap<? extends K,? extends V> h)
```
    Description copied from interface: Heap
    
    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.)
    
    Specified by:
    
    union in interface Heap<K,V>
    
    Overrides:
    
    union in class AbstractHeap<K,V>
  - decreaseKey
```
public void decreaseKey(java.util.Map.Entry<K,V> me,
                        K newkey)
```
    Description copied from interface: Heap
    
    Replace the key in the specified map entry with the specified smaller key.
    
    Specified by:
    
    decreaseKey in interface Heap<K,V>
    
    Specified by:
    
    decreaseKey in class AbstractHeap<K,V>
  - updateKey
```
public void updateKey(java.util.Map.Entry<K,V> me,
                      K newkey)
```
    Description copied from interface: Heap
    
    Replace the key in the specified map entry with the specified key, which may be either larger or smaller than its current key.
    
    Specified by:
    
    updateKey in interface Heap<K,V>
    
    Overrides:
    
    updateKey in class AbstractHeap<K,V>
  - delete
```
public void delete(java.util.Map.Entry<K,V> me)
```
    Description copied from interface: Heap
    
    Remove the specified map entry from the mapping.
    
    Specified by:
    
    delete in interface Heap<K,V>
    
    Specified by:
    
    delete in class AbstractHeap<K,V>
  - clear
```
public void clear()
```
    Description copied from interface: Heap
    
    Removes all entries from this Heap.
    
    Specified by:
    
    clear in interface Heap<K,V>
    
    Specified by:
    
    clear in class AbstractHeap<K,V>
  - size
```
public int size()
```
    Description copied from interface: Heap
    
    Returns the number of entries in this Heap.
    
    Specified by:
    
    size in interface Heap<K,V>
    
    Specified by:
    
    size in class AbstractHeap<K,V>
  - entries
```
public java.util.Collection<java.util.Map.Entry<K,V>> entries()
```
    Description copied from interface: Heap
    
    Returns a collection view of all the Map.Entrys in this Heap.
    
    Specified by:
    
    entries in interface Heap<K,V>
    
    Specified by:
    
    entries in class AbstractHeap<K,V>
  - setKey
```
protected final K setKey(java.util.Map.Entry<K,V> me,
                         K newkey)
```
    Description copied from class: AbstractHeap
    
    This method should set the key for the specified Map.Entry to the given newkey. Implementation is optional, but it is required if you use the default implementation of updateKey().
    
    Overrides:
    
    setKey in class AbstractHeap<K,V>
  - main
```
public static void main(java.lang.String[] args)
```
    Self-test function.

Class BinaryHeap<K,V>

Constructor Summary

Method Summary

Methods inherited from class net.cscott.jutil.AbstractHeap

Methods inherited from class java.lang.Object

Constructor Detail

BinaryHeap

BinaryHeap

BinaryHeap

BinaryHeap

Method Detail

insert

minimum

extractMinimum

union

decreaseKey

updateKey

delete

clear

size

entries

setKey

main