Priority queues are useful for any application that involves processing elements by priority.

In discussing FIFO queue applications in Chapter 4, we said that an operating system often maintains a queue of processes that are ready to execute. It is common, however, for such processes to have different priority levels, so that rather than using a standard queue, an operating system may use a priority queue to manage process execution.

In Section 4.8, “Application: Average Waiting Time,” we used queues to help us model a customer service system. This was a relatively simple model that generated all the information about the customers first, and then simulated servicing them. For more complex models it is possible to generate customer information during processing—consider, for example, that a man arrives at the service counter only to discover he incorrectly filled out a form; he needs to redo the form and get back in the queue. His reentry to the queue is a dynamic event that could not have been predicted ahead of time. Modeling this type of system is termed discrete event simulation and is an interesting area of study. A common approach with discrete event models is to maintain a priority queue of events. As events are generated they are enqueued, with a priority level equal to the time at which the event is to take place. Earlier events have higher priority. The event-driven simulation proceeds by dequeuing the highest-priority event (the earliest event available) and then modeling that event, which may generate subsequent events to be enqueued.

Priority queues are also useful for sorting data. Given a set of elements to sort, the elements can be enqueued into a priority queue, and then dequeued in sorted order (from largest to smallest). We look at how priority queues and their implementations can be used in sorting in Chapter 11.

The operations defined for the Priority Queue ADT include enqueuing elements and dequeuing elements, as well as testing for an empty or full-priority queue and determining the queue’s size. These operations are very similar to those specified for the FIFO queue discussed in Chapter 4. In fact, except for the information in the comments and the name and package of the interface, the queue interface and the priority queue interface are indistinguishable. Functionally, the difference between the two types of queues is due to how the dequeue operation is implemented. The Priority Queue ADT does not follow the “FIFO” approach; instead, it always returns the highest-priority element from the current set of enqueued elements, no matter when the element was enqueued. For our purposes we define highest priority as the “largest” element based on the indicated ordering of elements. Here is the interface:

//---------------------------------------------------------------------------
// PriQueueInterface.java         by Dale/Joyce/Weems               Chapter 9
//
// Interface for a class that implements a priority queue of T.
// The largest element as determined by the indicated comparison has the
// highest priority.
//
// Null elements are not allowed. Duplicate elements are allowed.
//---------------------------------------------------------------------------
package ch09.priorityQueues;

public interface PriQueueInterface<T>
{
  void enqueue(T element);
  // Throws PriQOverflowException if this priority queue is full;
  // otherwise, adds element to this priority queue.

  T dequeue();
  // Throws PriQUnderflowException if this priority queue is empty;
  // otherwise, removes element with highest priority from this
  // priority queue and returns it.

  boolean isEmpty();
  // Returns true if this priority queue is empty; otherwise, returns false.

  boolean isFull();
  // Returns true if this priority queue is full; otherwise, returns false.

  int size();
  // Returns the number of elements in this priority queue.
}

The exception objects mentioned in the comments are defined as part of the ch09. priorityQueues package. They are unchecked exceptions.

As with all of the ADTs we have studied, variations of the Priority Queue ADT exist. In particular, it is common to include operations that allow an application to reach into a priority queue to examine, manipulate, or remove elements. For some applications such operations are necessary. Consider the previously discussed use of priority queues for discrete event simulation. With some discrete event models the result of handling an event may affect other scheduled events, delaying or canceling them. The additional priority queue functionality allows them to be used for such models. Here though, we focus solely on the basic Priority Queue operations as listed in PriQueueInterface.

Enqueuing an element would be very easy with an unsorted array—simply insert it in the next available array slot, an O(1) operation. Dequeuing, however, would require searching through the entire array to find the largest element, an O(N) operation.

Dequeuing is very easy with this array-based approach: Simply return the last array element (which is the largest) and reduce the size of the queue; dequeue is a O(1) operation. Enqueuing, however, would be more expensive, because we have to find the place to insert the element. This is an O(log₂N) step if we use a binary search. Shifting the elements of the array to make room for the new element is an O(N) step, so overall the enqueue operation is O(N).

The SortedABPriQ class implements the PriQueueInterface using the approach outlined earlier. It provides two constructors, one of which allows the client to pass a Comparator argument to be used to determine priority, and the other which has no parameters, indicating that the natural order of the elements should be used. This is an unbounded array-based implementation. To enable easy testing it includes a toString method. The reader is invited to study the code found in the ch09.priorityQueues package. Here is a short program that demonstrates use of the SortedABPriQ class, followed by its output.

//---------------------------------------------------------------------------
// UseSortedABPriQ.java            by Dale/Joyce/Weems              Chapter 9
//
// Example use of the SortedABPriQ
//---------------------------------------------------------------------------
package ch09.apps;
import ch09.priorityQueues.*;

public class UseSortedABPriQ
{
  public static void main(String[] args)
  {
    PriQueueInterface<String> pq = new SortedABPriQ<String>();

    pq.enqueue("C");   pq.enqueue("O");    pq.enqueue("M");
    pq.enqueue("P");   pq.enqueue("U");    pq.enqueue("T");
    pq.enqueue("E");    pq.enqueue("R");

    System.out.println(pq);
    System.out.println(pq.dequeue());
    System.out.println(pq.dequeue());
    System.out.println(pq);
  }
}
     The output is:
     Priority Queue:   C  E  M  O  P  R  T  U

     U
     T

     Priority Queue:   C  E  M  O  P  R

Assume the linked list is kept sorted from largest to smallest. Dequeuing with this reference-based approach simply requires removing and returning the first list element, an operation that takes only a few steps. But enqueuing again is an O(N) operation, because we must search the list one element at a time to find the insertion location.

For this approach, the enqueue operation is implemented as a standard binary search tree insert operation. We know that operation requires O(log₂N) steps on average. Assuming access to the underlying implementation structure of the tree, we can implement the dequeue operation by returning the largest element, which is the rightmost tree element. We follow the right subtree references down, maintaining a trailing reference, until reaching a node with an empty right subtree. The trailing reference allows us to “unlink” the node from the tree. We then return the element contained in the node. This is also a O(log₂N) operation, on average.

The binary search tree approach is the best so far—it requires, on average, only O(log₂N) steps for both enqueue and dequeue. If the tree is skewed, however, the performance degenerates to O(N) steps for each operation. The time efficiency benefits depend on the tree remaining balanced. Unless a self-balancing tree is used it is likely the tree will become skewed—after all, elements will continually be removed from the far right of the tree only, which will result in a tree that is heavier on its left side. We can do better.

The next section presents a very clever approach, called the heap, that guarantees O(log₂N) steps, even in the worst case.

The implementation of binary trees we studied in Chapter 7 used a scheme in which the links from parent to children are explicit in the implementation structure. In other words, instance variables were declared in each node for the reference to the left child and the reference to the right child.

A binary tree can be stored in an array in such a way that the relationships in the tree are not directly represented by references, but rather are implicit in the positions used within the array to hold the elements.

Let us take a binary tree and store it in an array in such a way that the parent–child relationships are not lost. We store the tree elements in the array, level by level, from left to right. We call the array elements and store the index of the last tree element in a variable lastIndex, as illustrated in Figure 9.6. The tree elements are stored with the root in elements[0] and the last node in elements[lastIndex].

To implement the algorithms that manipulate the tree, we must be able to find the left and right children of a node in the tree. Comparing the tree and the array in Figure 9.6, we make the following observations:

Do you see the pattern? For any node elements[index], its left child is in elements[index * 2 + 1] and its right child is in elements[(index * 2) + 2] (provided that these child nodes exist). Notice that nodes from elements[(tree. lastIndex + 1) / 2] to elements[tree.lastindex] are leaf nodes.

Not only can we easily calculate the location of a node’s children, but we can also determine the location of its parent node, a required operation for reheapUp. This task is not an easy one in a binary tree linked together with references from parent to child nodes, but it is very simple in our implicit link implementation: elements[index]’s parent is in elements[(index - 1) / 2].

Because integer division truncates any remainder, (index - 1) / 2 is the correct parent index for either a left or right child. Thus, this implementation of a binary tree is linked in both directions: from parent to child, and from child to parent.

The array-based representation is simple to implement for trees that are full or complete, because the elements occupy contiguous array slots. If a tree is not full or complete, however, we must account for the gaps where nodes are missing. To use the array representation, we must store a dummy value in those positions in the array to maintain the proper parent–child relationship. The choice of a dummy value depends on the information that is stored in the tree. For instance, if the elements in the tree are nonnegative integers, a negative value can be stored in the dummy nodes; if the elements are objects, we can use a null value.

Figure 9.7 illustrates an incomplete tree and its corresponding array. Some of the array slots do not contain actual tree elements, but rather dummy values. The algorithms to manipulate the tree must reflect this situation. For example, to determine that the node in elements[index] has a left child, we must verify that (index * 2) + 1 <= lastIndex, and that the value in elements[(index * 2) + 1] is not the dummy value.

Although when there are many “holes” in the tree, the array-based binary tree implementation can waste a lot of space, in the case of the heap it is a perfect representation. The shape property of heaps tells us that the binary tree is complete, so we know that it is never unbalanced. Thus, we can easily store the tree in an array with implicit links without wasting any space. Figure 9.8 shows how the values in a heap would be stored in the array-based representation.

If a heap with N elements is implemented this way, the shape property says that the heap elements are stored in N consecutive slots in the array, with the root element in the first slot (index 0) and the last leaf node in the slot with index lastIndex = N – 1. Therefore, when implementing this approach there is no need for dummy values—there are never gaps in the tree.

Recall that when we use this representation of a binary tree, the following relationships hold for an element at position index:

• If the element is not the root, its parent is at position (index - 1) / 2.

• If the element has a left child, the child is at position (index * 2) + 1.

• If the element has a right child, the child is at position (index * 2) + 2.

These relationships allow us to efficiently calculate the parent, left child, or right child of any node. Also, because the tree is complete, no space is wasted using the array representation. Time efficiency and space efficiency! We make use of these features in our heap implementation.

Rather than directly use an array to implement our heaps we use the Java library’s ArrayList class. This allows us to create a generic heap without needing to deal with the troublesome issues surrounding the use of generics and arrays in Java. An ArrayList is essentially just a wrapper around an array—therefore, the use of an ArrayList does not cost much, if anything, in terms of efficiency. This is especially true since we design our heap-based priority queue to be of a fixed capacity, and therefore prevent the use of the automatic, time-inefficient copying of the underlying array that occurs when an ArrayList object needs to be resized. Furthermore, the code only ever adds or removes elements at the “end” of the ArrayList—adding or removing anywhere else would require costly element shifting.

Here is the beginning of our HeapPriQ class. As you can see, it implements PriQueueInterface. Because it implements a priority queue, we placed it in the ch09. priorityQueues package. Also, note that both constructors require an integer argument, used to set the size of the underlying ArrayList. As with several of our ADTs, one constructor accepts a Comparator argument and the other creates a Comparator based on the “natural order” of T. The isEmpty, isFull, and size operations are trivial.

//---------------------------------------------------------------------------
// Heap.java               by Dale/Joyce/Weems                      Chapter 9
// Priority Queue using Heap (implemented with an ArrayList)
//
// Two constructors are provided: one that use the natural order of the
// elements as defined by their compareTo method and one that uses an
// ordering based on a comparator argument.
//---------------------------------------------------------------------------

package ch09.priorityQueues;

import java.util.*;  // ArrayList, Comparator

public class HeapPriQ<T> implements PriQueueInterface<T>
{
  protected ArrayList<T> elements; // priority queue elements
  protected int lastIndex;         // index of last element in priority queue
  protected int maxIndex;          // index of last position in ArrayList

  protected Comparator<T> comp;

  public HeapPriQ(int maxSize)
  // Precondition: T implements Comparable
  {
    elements = new ArrayList<T>(maxSize);
    lastIndex = -1;
    maxIndex = maxSize - 1;

    comp = new Comparator<T>()
    {
       public int compare(T element1, T element2)
       {
         return ((Comparable)element1).compareTo(element2);
       }
    };
  }

  public HeapPriQ(int maxSize, Comparator<T> comp)
  // Precondition: T implements Comparable
  {
    elements = new ArrayList<T>(maxSize);
    lastIndex = -1;
    maxIndex = maxSize - 1;

    this.comp = comp;
  }

  public boolean isEmpty()
  // Returns true if this priority queue is empty; otherwise, returns false.
  {
    return (lastIndex == -1);
  }

  public boolean isFull()
  // Returns true if this priority queue is full; otherwise, returns false.

  {
    return (lastIndex == maxIndex);
  }

  public int size()
  // Returns the number of elements on this priority queue.
  {
    return lastIndex + 1;
  }

We next look at the enqueue method, which is the simpler of the two transformer methods. Assuming the existence of a reheapUp helper method, as specified previously, the enqueue method is

public void enqueue(T element) throws PriQOverflowException
// Throws PriQOverflowException if this priority queue is full;
// otherwise, adds element to this priority queue.
{
  if (lastIndex == maxIndex)
    throw new PriQOverflowException("Priority queue is full");
  else
  {
    lastIndex++;
    elements.add(lastIndex,element);
    reheapUp(element);
  }
}

If the heap is already full, the appropriate exception is thrown. Otherwise, we increase the lastIndex value, add the element to the heap at that location, and call the reheapUp method. Of course, the reheapUp method is doing all of the interesting work. Let us look at it more closely.

The reheapUp algorithm starts with a tree whose last node is empty; we call this empty node the “hole.” We swap the hole up the tree until it reaches a spot where the element argument can be placed into the hole without violating the order property of the heap. While the hole moves up the tree, the elements it is replacing move down the tree, filling in the previous location of the hole. This situation is illustrated in Figure 9.9.

The sequence of nodes between a leaf and the root of a heap can be viewed as a sorted linked list. This is guaranteed by the heap’s order property. The reheapUp algorithm is essentially inserting an element into this sorted linked list. As we progress from the leaf to the root along this path, we compare the value of element with the value in the hole’s parent node. If the parent’s value is smaller, we cannot place element into the current hole, because the order property would be violated, so we move the hole up. Moving the hole up really means copying the value of the hole’s parent into the hole’s location. Now the parent’s location is available, and it becomes the new hole. We repeat this process until (1) the hole is the root of the heap or (2) element’s value is less than or equal to the value in the hole’s parent node. In either case, we can now safely copy element into the hole’s position.

This approach requires us to be able to find a given node’s parent quickly. This task appears difficult, based on our experiences with references that can be traversed in only one direction. But, as we saw earlier, it is very simple with our implicit link implementation:

• If the element is not the root, its parent is at position (index - 1) / 2.

Here is the code for the reheapUp method:

private void reheapUp(T element)
// Current lastIndex position is empty.
// Inserts element into the tree and ensures shape and order properties.
{
  int hole = lastIndex;
  while ((hole > 0)    // hole is not root and element > hole's parent
         &&
    (comp.compare(element, elements.get((hole - 1) / 2)) > 0))
    {
    // move hole's parent down and then move hole up
    elements.set(hole,elements.get((hole - 1) / 2));
    hole = (hole - 1) / 2;
  }
  elements.set(hole, element);  // place element into final hole
}

This method takes advantage of the short-circuit nature of Java’s && operator. If the current hole is the root of the heap, then the first half of the while loop control expression

(hole > 0)

is false, and the second half

(element.compareTo(elements.get((hole - 1) / 2)) > 0))

is not evaluated. If it was evaluated in that case, it would cause an IndexOutOfBoundsException to be thrown.

Finally, we look at the dequeue method. As for enqueue, assuming the existence of the helper method, in this case the reheapDown method, the dequeue method is relatively simple:

public T dequeue() throws PriQUnderflowException
// Throws PriQUnderflowException if this priority queue is empty;
// otherwise, removes element with highest priority from this
// priority queue and returns it.
{
  T hold;      // element to be dequeued and returned
  T toMove;    // element to move down heap

  if (lastIndex == -1)
    throw new PriQUnderflowException("Priority queue is empty");
  else

  {
    hold = elements.get(0);              // remember element to be returned
    toMove = elements.remove(lastIndex); // element to reheap down
    lastIndex--;                         // decrease priority queue size
    if (lastIndex != -1)                 // if priority queue is not empty
       reheapDown(toMove);                  // restore heap properties
    return hold;                         // return largest element
  }
}

If the heap is empty, the appropriate exception is thrown. Otherwise, we first store a reference to the root element (the maximum element in the tree), so that it can be returned to the client program when finished. We also store a reference to the element in the “last” position and remove it from the ArrayList. Recall that this is the element used to move into the hole vacated by the root element, so we call it the toMove element. We decrement the lastIndex variable to reflect the new bounds of the heap and, assuming the heap is not now empty, pass the toMove element to the reheapDown method. The only thing remaining to do is to return the saved value of the previous root element, the hold variable, to the client.

Look at the reheapDown algorithm more closely. In many ways, it is similar to the reheapUp algorithm. In both cases, we have a “hole” in the tree and an element to be placed into the tree so that the tree remains a heap. In both cases, we move the hole through the tree (actually moving tree elements into the hole) until it reaches a location where it can legally hold the element. The reheapDown operation, however, is a more complex operation because it is moving the hole down the tree instead of up the tree. When we are moving down, there are more decisions to make.

When reheapDown is first called, the root of the tree can be considered a hole; that position in the tree is available, because the dequeue method has already saved the contents in its hold variable. The job of reheapDown is to “move” the hole down the tree until it reaches a spot where element can replace it. See Figure 9.10.

Before we can move the hole, we need to know where to move it. It should move either to its left child or to its right child, or it should stay where it is. Assume the existence of another helper method, called newHole, that provides us this information. The newHole method accepts arguments representing the index of the hole (hole), and the element to be inserted (element). The specification for newHole is

private int newHole(int hole, T element)
// If either child of hole is larger than element, return the index
// of the larger child; otherwise, return the index of hole.

Given the index of the hole, newHole returns the index of the next location for the hole. If newHole returns the same index that is passed to it, we know the hole is at its final location. The reheapDown algorithm repeatedly calls newHole to find the next index for the hole, and then moves the hole down to that location. It does this until newHole returns the same index that is passed to it. The existence of newHole simplifies reheapDown so that we can now create its code:

private void reheapDown(T element)
// Current root position is "empty";
// Inserts element into the tree and ensures shape and order properties.
{
  int hole = 0;      // current index of hole
  int next;          // next index where hole should move to

  next = newHole(hole, element);   // find next hole
  while (next != hole)
  {
    elements.set(hole,elements.get(next));  // move element up
    hole = next;                            // move hole down
    next = newHole(hole, element);          // find next hole
  }
  elements.set(hole, element);              // fill in the final hole
}

Now the only thing left to do is create the newHole method. This method does quite a lot of work for us. Consider Figure 9.10 again. Given the initial configuration, newHole should return the index of the node containing J, the right child of the hole node; J is larger than either the element (E) or the left child of the hole node (H). Thus, newHole must compare three values (the values in element, the left child of the hole node, and the right child of the hole node) and return the index of the greatest value. Think about that. It does not seem very hard, but it does require quite a few steps:

Other approaches to this algorithm are possible, but they all require about the same number of comparisons. One benefit of the preceding algorithm is that if element is tied for being the largest of the three arguments, its index is returned. This choice increases the efficiency of our program because in this situation we want the hole to stop moving (reheapDown breaks out of its loop when the value of hole is returned). Trace the algorithm with various combinations of arguments to convince yourself that it works.

Our algorithm applies only to the case when the hole node has two children. Of course, the newHole method must also handle the cases where the hole node is a leaf and where the hole node has only one child. How can we tell if a node is a leaf or if it has only one child? Easily, based on the fact that our tree is complete. First, we calculate the expected position of the left child; if this position is greater than lastIndex, then the tree has no node at this position and the hole node is a leaf. (Remember, if it does not have a left child, it cannot have a right child because the tree is complete.) In this case newHole just returns the index of its hole parameter, because the hole cannot move anymore. If the expected position of the left child is equal to lastIndex, then the node has only one child, and newHole returns the index of that child if the child’s value is larger than the value of element.

Here is the code for newHole. As you can see, it is a sequence of if-else statements that capture the approaches described in the preceding paragraphs.

private int newHole(int hole, T element)
// If either child of hole is larger than element, return the index
// of the larger child; otherwise, return the index of hole.
{
  int left = (hole * 2) + 1;
  int right = (hole * 2) + 2;

  if (left > lastIndex)
    // hole has no children
    return hole;
  else
  if (left == lastIndex)
    // hole has left child only
    if (comp.compare(element, elements.get(left)) < 0)
      // element < left child
       return left;
    else
      // element >= left child
      return hole;
  else
  // hole has two children
  if (comp.compare(elements.get(left), elements.get(right)) < 0)
    // left child < right child
    if (comp.compare(elements.get(right), element) <= 0)
      // right child <= element
       return hole;
    else
      // element < right child
      return right;
  else
  // left child >= right child
  if (comp.compare(elements.get(left), element) <= 0)
    // left child <= element
     return hole;
  else
    // element < left child
    return left;
}

To allow us to test our heap we include the following toString method within its implementation:

@Override
public String toString()
// Returns a string of all the heap elements.
{
  String theHeap = new String("the heap is:
");
  for (int index = 0; index <= lastIndex; index++)
    theHeap = theHeap + index + ". " + elements.get(index) + "
";
  return theHeap;
}

This toString method simply returns a string indicating each index used in the heap, along with the corresponding element contained at that index. It allows us to devise test programs that create and manipulate heaps, and then displays their structure.

Suppose you enqueue the strings “J”, “A”, “M”, “B”, “L”, and “E” into a new heap. How would you draw our abstract view of the ensuing heap? Which values would be in which ArrayList slots? Suppose you dequeue an element and print it? Which element would be printed, and how would the realigned heap appear?

To demonstrate how you might declare and use a heap in an application we provide a short example of a program that performs those operations, and we show the output from the program. Were your predictions correct?

//---------------------------------------------------------------------------
// UseHeap.java               by Dale/Joyce/Weems                   Chapter 9
//
// Example of a simple use of the HeapPriQ.
//---------------------------------------------------------------------------
package ch09.apps;

import ch09.priorityQueues.*;

public class UseHeap
{
  public static void main(String[] args)
  {
    PriQueueInterface<String> h = new HeapPriQ<String>(10);
    h.enqueue("J");
    h.enqueue("A");
    h.enqueue("M");
    h.enqueue("B");
    h.enqueue("L");
    h.enqueue("E");

    System.out.println(h);

    System.out.println(h.dequeue() + "
");

    System.out.println(h);
  }
}

Here is the output from the program, with our abstract view of the heap, both before and after dequeuing the largest element, drawn to the right:

How efficient is the heap implementation of a priority queue? The constructors, isEmpty, isFull, and size methods are trivial, so we examine only the operations to add and remove elements. The enqueue and dequeue methods both consist of a few basic operations plus a call to a helper method. The reheapUp method creates a slot for a new element by moving a hole up the tree, level by level; because a complete tree is of minimum height, there are at most ⌊log₂N⌋ levels above the leaf level (N = number of elements). Thus, enqueue is an O(log₂N) operation. The reheapDown method is invoked to fill the hole in the root created by the dequeue method. This operation moves the hole down in the tree, level by level. Again, there are at most ⌊log₂N⌋ levels below the root, so dequeue is also an O(log₂N) operation.

How does this implementation compare to the others we mentioned in Section 9.2, “Priority Queue Implementations”? As discussed there, the only approach with comparable efficiency is the binary search tree approach; however, in that case the efficiency of the operations depends on the shape of the tree. When the tree is bushy, both dequeue and enqueue are O(log₂N) operations. In the worst case, if the tree degenerates to a linked list, both enqueue and dequeue have O(N) efficiency.

Overall, the binary search tree looks good if it is balanced. It can, however, become skewed, which reduces the efficiency of the operations. The heap, by contrast, is always a tree of minimum height. It is not a good structure for accessing a randomly selected element, but that is not one of the operations defined for priority queues. The accessing protocol of a priority queue specifies that only the largest (or highest-priority) element can be accessed. For the operations specified for priority queues; therefore, the heap is an excellent choice.