Data Structures Project 3
Due: Monday, Nov 20, 2000, 11am. 100 points.
In this project, you will implement the
Priority Queue interface using a heap. Your constructor for making a
Priority Queue should be able to take a Comparator object as an
argument, and it should use Comparators to do all comparisons (your
default Comparator should be able to perform comparisons of Integer
objects).
Your heap data structure should be built using the binary tree
interface, and this interface should be implemented using an array.
Note: you may augment your binary tree class to add
a method for identifying the last node. In addition,
if you run out of space for nodes, double the length of array.
If the number of elements in the priority queue becomes less than
half the length of the array, copy elements into another array half as long.
The assignment, then, is to build a class that implements
each method in the Priority Queue ADT.
Since the Priority Queue is implemented using a heap, which in turn is implemented
using a simple binary tree, this assignment involves you producting other classes as well:
- HeapPriorityQueue, which uses a heap to implement the
priority queue ADT.
Note: your heap must use a binary tree to implement a heap
(but can rely on additional methods than just the Simple Binary
Tree methods, e.g., to keep track of the ``last'' node).
- MyBinaryTree, which implements the
binary tree ADT using an array
(and can optionally provide additional methods than just those
included in the Binary Tree ADT).
In addition, your HeapPriorityQueue
implementation should have a constructor:
HeapPriorityQueue(Sequence S),
which takes a sequence
of Object Combinators (see ComposedObj.java).
(Use the implementation of Sequence from project 2. If you don't quite
trust your implementation, you may use an array of combinators instead of
a sequence as the input parameter.) The construction must be bottom up.
You may assume unique keys.
In addition to the priority Queue, write a HeapSorter class which provides
the following method
- Sequence sortBound(Sequence S).
This method takes in
a sequence of combinators and first constructs a Priority Queue in O(n). It then inserts
(using insertItem) two
more new combinators, of -Integer.MAX_VALUE & Dummy.NULL_ELEMENT
and Integer.MAX_VALUE & Dummy.NULL_ELEMENT,
into the Priority Queue. Finally, the method deletes elements
(with the minimum key) from the priority queue, one at a time, inserting them into a new sorted
Sequence which it then returns. Thus the returned sequence has two extra elements,
one at the beginning and another at the end. (Again, you may use an array in place of
a sequence).
Your main method must read a list of integers from a file, input.txt ,
then make combinator objects with the integers as the keys and
Dummy.NULL_ELEMENT as the elements. It then uses HeapSorter.sortBound() method to sort
the objects. Finally, it writes the
the sorted sequence (or array) back into the file output.txt.
The following files are provided to help guide your software
development: