A priority queue is simply a queue in which
the elements are ordered by some designated priority instead of by
arrival time. (In the text another requirement is imposed, that
elements of the same priority have FIFO ordering, but we will not use this
requirement.) Viewed another way, a FIFO queue is a priority queue in
which arrival time serves as the priority. One efficient implementation
of a priority queue uses a heap (a min heap, assuming that a lower value indicates
a higher priority). These exercises lead you through one such implementation,
which you will use for the next part of your project.
Using a Heap to Implement a Priority Queue
Create a subdirectory pqlab in your cs220 directory for the work
that you will do in this lab.
The Prioritizable Interface
For an item to be inserted into a priority queue, it must have an
associated priority. One way to do this is to insist that it have
a public int priority() method that returns its priority.
Write a Prioritizable interface that requires such a method.
The PriorityQueue Interface
A priority queue is an abstract data type whose methods look a lot like
those of a queue: enqueue, dequeue, isEmpty, isFull. The main difference
is that objects enqueued in and dequeued from
a priority queue must have a priority, which for us means they must be
Write a PriorityQueue interface with these requirements.
The HeapPriorityQueue Class, Part I
As mentioned above, one way to implement a priority queue is with a heap.
Start writing a class HeapPriorityQueue that implements the
PriorityQueue interface as follows:
- Use an array to store the heap elements (which must be of type
Prioritizable). Remember that this can
be done efficiently since a heap is a complete binary tree.
You will also need to keep track of how many
elements are actually in the heap.
- Write a constructor that creates a 100-element array and initializes
the number of elements to 0.
- Write enqueue; remember the algorithm:
Since you will be doing a lot of moving around in the heap -- going from
a node to its parent or one of its children -- write the following methods
to get the index of the node you want: int parent(int i), int rightchild(int i),
and int leftchild(int i). This is much nicer than having the calculations
all over the program.
- Add the item to the end of the heap.
- Increment the numItems counter.
- Reheapify up, that is, bubble the item up until it is greater than or
equal to its parent (remember this is a min heap). To keep the
enqueue method clean, do this in a separate method.
- For debugging purposes, write a toString method that
returns a string containing the array elements. Remember that each
element is an object, so it may be arbitrarily complex.
put the elements on separate lines in the string
(use "\n" to insert a line break into a string),
which takes a lot of output space but
makes it easy to see where one element
stops and the next starts
Or, for a more compact representation, keep the string on one line but enclose
each element in ().
Note that this will NOT give the elements in priority order;
it will just show you a level order traversal of the heap.
The TestPQ Class, Part I
This is a good place to stop and do some testing.
- First you will need
a class that implements the Prioritizable interface so you can create objects
to put in your priority queue. Write a class PriorityItem that
implements Prioritizable. A PriorityItem should hold an object and an
integer priority, with methods to return each. It should also have
a toString method that returns a string containing both the object and
- Now write a class TestPQ that creates and adds items to a
PriorityQueue (which you will implement using a HeapPriorityQueue).
Use a loop to repeatedly read strings and integer priorities from
the user; store each string/priority pair in a PriorityItem object and
enqueue it in your priority queue. After each enqueue, print your heap.
If it isn't doing the right thing,
figure out what's wrong and fix it.
The HeapPriorityQueue Class, Part II
Once you're convinced that the constructor and enqueue method for the
HeapPriorityQueue class are correct, write the dequeue, isEmpty, and
isFull methods. For now, assume that the queue is full if the array
is full. Remember the dequeue algorithm:
Be sure to use your parent, leftchild, and rightchild methods to keep
your code clean. You may want to write some other methods of this sort
as well -- e.g., int minchild(int i) could return the index of the smallest
- Remove the item from the top of the heap.
- Replace it with the last item in the heap.
- Decrement the numItems counter.
- Reheapify down, that is, bubble the top item down until it is
smaller than either of its children.
- Return the item you removed from the top of the heap.
The TestPQ Class, Part II
Now modify your TestPQ class so that after enqueueing the values entered
by the user, it enters a loop that successively dequeues and prints
each item from the priority queue.
You should get the items in
sorted order (by priority).
What to Turn In
Turn in hardcopy of each of your .java files: Prioritizable.java,
PriorityQueue.java, HeapPriorityQueue.java, PriorityItem.java, and
tar your pqlab directory and e-mail it to email@example.com with
cpsc220 pqlab in the subject line.