CS220 Lab
Using a Heap to Implement a Priority Queue

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, since 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.

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.
      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.
    4. 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. You can 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.

  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, print your heap. If it isn't doing the right thing, figure out what's wrong and fix it.

  5. 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 child.

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