Your assignment is to take an existing, inefficient implementation of a priority queue and modify it, creating a more efficient implementation that uses a heap. The actual amount of code that you need to produce is relatively small, giving you a chance to get used to Java before we try something more difficult. One of the major goals here is to understand what the various pieces of the program are doing.
You are provided with a number of different files that implement an inefficient version of a priority queue. The files are accessible on the web; this page contains the necessary links. The files are described below.
PriorityQueue.java: This is the file that you will have to change. It contains code for an abstract class PriorityQueue. The class is abstract because one of its methods is abstract (i.e., its code is unspecified). Abstract classes cannot be instantiated, but their subclasses can if they provide code to implement the abstract methods. PriorityQueue's public methods are
PQTest.java: This file contains two classes: PQTest, an applet/application for testing the priority queue, and PQString, a class that implements a priority queue on strings using alphabetical order. PQString is a subclass of the abstract class PriorityQueue; it overrides the before method to provide an ordering on items in the priority queue.
PQTest.htm: This is an html document for displaying the PQTest applet. You don't actually have to use this unless you want to run it as an applet. You can just as well compile and run it as a console application.
Modify the file PriorityQueue.java so that it is more efficient by replacing the current inefficient implementation with a new implementation that uses a heap. This is the only file that you should need to change.
Instead of using an array as described in the text, your heap should use the class Vector. The current, inefficient version of PriorityQueue also uses Vector and you should be able to get some idea of how vectors are used by examining the code. The advantage of vectors is that they automatically grow when needed, in contrast to arrays, which have a fixed size.
For access to elements, a Vector acts more or less like an array, except you use v.elementAt(i) instead of v[i]. You can assign a value to position i within a Vector by using setElementAt(i). The current size of the vector v is given by v.size(). The method v.addElement(Object) adds the given Object as the last element in v. You will probably also want to make use of removeElementAt(int) which removes the element at the given location; it also moves any following elements to fill in the empty spot. You should also take a look at java.util.Vector in the Java API---look at the online help in MS Developer Studio or the Java API Documentation at javasoft on the Web.
Side Comment: Your version of PriorityQueue will be more efficient than original version, but you won't be able to notice this by timing how fast things run in the testing program we provide. This is because the testing program always examines the entire contents of the Priority Queue after each operation in order to display a string representation of the priority queue. Presumably, if we weren't displaying the priority queue after each operation, then your new version would be noticably faster for large queues.
The description given here is for running the program using Microsoft Developer Studio/Visual J++ 6.0. You don't have to use this software; there are several other products that can compile and run Java code.
See the MS Developer Studio handout for basic information on how to run Developer Studio, create projects, add and delete files, compile, run and debug your program, etc.
We want to see two things:
To run PQTest as an applet outside of Developer Studio: Save PQTest.htm in your project directory and double click on it. This should launch your favorite browser and load the applet PQTest.class.
To run PQTest as a stand-alone application outside of Developer Studio: After compiling, there should be a file Project1.exe (or some other number) in your project directory produced by Developer Studio. Double click on it.