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 |
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 java.lang.Object |
clone,
equals,
finalize,
getClass,
hashCode,
notify,
notifyAll,
toString,
wait,
wait,
wait |
Heap
public Heap()
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 insertednewData
- 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 insertednewData
- 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