The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Queues and Priority Queues Array Implementation of Priority Queue
 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter Search the VIAS Library  |  Index

Array Implementation of Priority Queue

In the implementation of the Priority Queue, every time we specify the type of the items in the queue, we specify the abstract class Comparable. For example, the instance variables are an array of Comparables and an integer:

public class PriorityQueue {
    private Comparable[] array;
    private int index;
}

As usual, index is the index of the next available location in the array. The instance variables are declared private so that other classes cannot have direct access to them.

The constructor and empty are similar to what we have seen before. I chose the initial size for the array arbitrarily.

    public PriorityQueue () {
        array = new Comparable [16];
        index = 0;
    }

    public boolean empty () {
        return index == 0;
    }

insert is similar to push:

    public void insert (Comparable item) {
        if (index == array.length) {
            resize ();
        }
        array[index] = item;
        index++;
    }

I omitted the implementation of resize. The only substantial method in the class is remove, which has to traverse the array to find and remove the largest item:

    public Comparable remove () {
        if (index == 0) return null;

        int maxIndex = 0;

        // find the index of the item with the highest priority
        for (int i=1; i<index; i++) {
            if (array[i].compareTo (array[maxIndex]) > 0) {
                maxIndex = i;
            }
        }
        Comparable result = array[maxIndex];

        // move the last item into the empty slot
        index--;
        array[maxIndex] = array[index];
        return result;
   }

As we traverse the array, maxIndex keeps track of the index of the largest element we have seen so far. What it means to be the "largest" is determined by compareTo. In this case the compareTo method is provided by the Integer class, and it does what we expect---larger (more positive) numbers win.
Home Queues and Priority Queues Array Implementation of Priority Queue

Last Update: 2011-01-24