CS 410 Fall 99
Programming Assignment 1
Due Tuesday, September 14

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.

What are all these files?

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

abstract boolean before(Object,Object)
returns true iff the first Object comes before the second Object
void insert(Object)
place an item into the queue
boolean isEmpty()
check if the queue is empty
Object peek()
return the least item in the queue
Object get()
return the least item in the queue after deleting it
void clear()
remove everything from the queue
int size()
return the number of items in the queue
String toString()
return a String that indicates the contents of the priority queue

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.

What do I have to do?

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.

How do I run the program?

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.

  1. Start Visual J++ and create a new project for a console application. Make sure you use the Browse... button to create the project folder in an area where you can keep files.   You're supposed to have your own personal directory on the "Z:" drive that is not readable by anyone else. At this point, you should have a project workspace that contains no classes and no files except the project and workspace files and the template class1.java.
  2. Right-click on the links above and store the files PriorityQueue.java and PQTest.java (and PQTest.htm if you want) in your newly created project folder.
  3. Insert the files into the project and remove class1.java from the project. You should be able to see the new files in the Project Explorer window.
  4. Set the configuration to Debug. In Project menu -> Project Properties... -> Launch tab, check that the initial class is set to PQTest(main). Check "Launch as console application."
  5. At this point you're ready to run.

What do I turn in?

We want to see two things:

  1. a printout of your new version of the file PriorityQueue.java, and
  2. the output from the jview.exe window (not the green application window!) that appears when PQTest is run as a console application using your new PriorityQueue. We want you to hit each of the twelve month buttons in order from jan to dec, then we want you to hit the Get button until the Priority Queue is empty again. This should generate output in the jview.exe window.

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.