CS220 Lab
Using a Heap to Implement a Priority Queue

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.

Create a subdirectory pqlab in your cs220 directory for the work that you will do in this lab.

  1. 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.

  2. 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 Prioritizable.

    Write a PriorityQueue interface with these requirements.

  3. 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:

    1. 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.
    2. Write a constructor that creates a 100-element array and initializes the number of elements to 0.
    3. 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.
    4. 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.

  4. The TestPQ Class, Part I

    This is a good place to stop and do some testing.

    1. 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 the priority.

    2. 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.

    3. 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.

    4. 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 TestPQ.java. Also tar your pqlab directory and e-mail it to bloss@roanoke.edu with cpsc220 pqlab in the subject line.