org.locomotive.util.data
Class Heap

java.lang.Object
  |
  +--org.locomotive.util.data.DataTree
        |
        +--org.locomotive.util.data.Heap

public class Heap
extends DataTree

this class implements a heap ADT. it is useful for implementing priority queues among other things. It requires TreeNode class and some implementation of the ComparisonKey class. an enumeration may be created from it by using the elements() method

See Also:
TreeNode, IntegerKey, DataTree

Inner Class Summary
 class Heap.HeapIterator
          HeapIterator class creates a pointer to a node in a heap, thus allowing one to access any item in a heap, not just the first
 
Inner classes inherited from class org.locomotive.util.data.DataTree
DataTree.TreeNode
 
Fields inherited from class org.locomotive.util.data.DataTree
count, root
 
Constructor Summary
Heap()
           
 
Method Summary
 java.util.Enumeration elements()
          creates an enumeration of the heap
 DataTree.TreeNode find(ComparisonKey key)
          Search for an object (obj) in the heap such that obj.equals(key) is true.
 void insert(ComparisonKey newKey)
          this method inserts a ComparisonKey object into the heap in an appropriate place.
 void insert(ComparisonKey newKey, java.lang.Object newData)
          this method inserts a ComparisonKey object into the heap in an appropriate place
 boolean isEmpty()
          returns true if the heap is empty
 DataTree.TreeNode peek()
          Look at maximum element without removing it.
 java.lang.Object remove()
          this method removes the highest-valued element from the heap
 
Methods inherited from class org.locomotive.util.data.DataTree
root, size
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Heap

public Heap()
Method Detail

insert

public void insert(ComparisonKey newKey,
                   java.lang.Object newData)
this method inserts a ComparisonKey object into the heap in an appropriate place
Overrides:
insert in class DataTree
Parameters:
newObject - the key of the object to be inserted
newData - the data held in the new node PostCondition: the heap is reheapified

insert

public void insert(ComparisonKey newKey)
this method inserts a ComparisonKey object into the heap in an appropriate place. Used when the data held is the key
Overrides:
insert in class DataTree
Parameters:
newObject - the key of the object to be inserted
newData - the data held in the new node PostCondition: the heap is reheapified

remove

public java.lang.Object remove()
                        throws ComparisonKeyException
this method removes the highest-valued element from the heap

peek

public DataTree.TreeNode peek()
Look at maximum element without removing it.

isEmpty

public boolean isEmpty()
returns true if the heap is empty
Overrides:
isEmpty in class DataTree

find

public DataTree.TreeNode find(ComparisonKey key)
Search for an object (obj) in the heap such that obj.equals(key) is true. Return a pointer to the object and make the node where it is found the current node (e.g., for a subsequent remove() call). returns null if the object is not found If more than one object would match, return the *first * such object in the heap.
Overrides:
find in class DataTree

elements

public java.util.Enumeration elements()
creates an enumeration of the heap