As we discussed in class, a priority queue is simply a queue in which
the elements are ordered by some designated priority instead of by
arrival time. 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, since a lower value indicates
a higher priority). These exercises lead you through one such implementation,
which you will use for part 3 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:
- 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 printHeap method that
prints each element of the array, one
per line. Note that this will NOT print 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, use your
printHeap method to look at the heap.
If the heap 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:
- 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 won't need the printHeap method
anymore except to debug if things aren't working.) 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.