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.

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;

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

Last Update: 2011-01-24