Beginning Algorithms (2006)

Chapter 8

Understanding Priority Queues

A priority queue is a queue that supports accessing items from the largest to the smallest. Unlike a simple queue that supports accessing items in the same order that they were added to the queue, or a stack, which supports accessing the items based on how recently they were added to the stack, a priority queue enables much more flexible access to the objects contained in the structure.

A priority queue allows a client program to access the largest item at any time. (Don’t be concerned about the term largest, as a simple reverse comparator can switch that around to be smallest at no cost.) The point is that the priority queue has a mechanism to determine which item is the largest (a comparator) and provides access to the largest item in the queue at any given time.

A priority queue is a more general form of queue than an ordinary first-in, first-out (FIFO) queue or lastin, first-out (LIFO) stack. You can imagine a priority queue in which the comparator supplied to it was based on time since insertion (FIFO) or time of insertion (LIFO). A priority queue could be used in this way to provide exactly the same feature set as a normal stack or queue.

A Simple Priority Queue Example

Imagine you have a priority queue that contains letters. Your imaginary client program is going to insert the letters from a series of words into the queue. After each word is inserted, the client will remove the largest letter from the queue. Figure 8-1 shows the letters to use.

T

H

E

Q

U

I

C

K

B

R

O

W

N

F

O

X

J

U

M

P

E

D

O

V

E

R

T

H

E

L

A

Z

Y

D

O

G

Figure 8-1: Input to the example priority queue.

174

Priority Queues

You begin by adding the letters from the first word into the priority queue. Figure 8-2 shows the situation after you do this.

Q

U

I

C

K

B

R

O

W

N

F

O

X

J

U

M

P

E

D

O

V

E

R

T

H

E

L

A

Z

Y

D

O

G

Priority	H	T
Queue

E

Figure 8-2: The letters from the first word have been added to the priority queue.

The largest letter in the priority queue is highlighted. When the client program removes the largest item, it becomes the item that is returned. We depicted the priority queue as a pool of letters, rather than as a list of letters with a specific order. Most priority queues hold their elements as a list, but it is important to understand that this is an implementation detail, and not part of the priority queue abstraction.

175

Chapter 8

Figure 8-3 shows the situation after the client takes the largest item off the priority queue.

Q

U

I

C

K

B

R

O

W

N

F

O

X

J

U

M

P

E

D

O

V

E

R

T

H

E

L

A

Z

Y

D

O

G

Priority	H
Queue

E

OUTPUT

T

Figure 8-3: The largest letter is removed from the priority queue.

176

Priority Queues

The client program adds all the letters from the second word into the priority queue; then it removes the largest one, leading to the situation shown in Figure 8-4.

B

R

O

W

N

F

O

X

J

U

M

P

E

D

O

V

E

R

T

H

E

L

A

Z

Y

D

O

G

	Priority		Q
		H	K
	Queue
		I	C
			E

OUTPUT

T U

Figure 8-4: The second word is added to the queue and the largest letter is removed.

177

Chapter 8

The process is repeated for the third word, as shown in Figure 8-5.

F O X

J

U

M

P

E

D

O

V

E

R

T

H

E

L

A

Z

Y

D

O

G

	Priority		Q
		H	K	N	B
	Queue
			O
		I	C		R
			E

OUTPUT

T U W

Figure 8-5: The third word in the example is processed.

178

Priority Queues

By now, you’ll be getting the idea of how the priority queue works, so we’ll skip to the result in the example, after all the words have been processed in the same way (see Figure 8-6).

D

E

O

E

G

L

Priority

A

Q

N

O

D

Queue

H

K

B

E

J

O

R

M

I

E

C

O

P

R

OUTPUT

H

F

T

U

W

X

U

V

T

Z

Y

Figure 8-6: The final state of the example priority queue.

In this final state, two items that are the equal largest among the remaining items are highlighted in the priority queue. The next call by the client program to remove the largest item could remove either of these two items.

Working with Priority Queues

In the Try It Out examples that follow, you implement three priority queues. They all implement the Queue interface from Chapter 4, and vary from the very simple to a quite complex version based on a heap structure. There is no need to add operations to the Queue interface; all a priority queue does, in effect, is alter the semantics of the dequeue() method to return the largest item currently in the queue.

Try It Out

Creating an AbstractPriorityQueue Test Case

First you define a test that your various priority queue implementations will need to pass. As you did with the sorting algorithms, you define the test itself in an abstract test case, leaving a factory method as a placeholder. When you want to test a specific implementation of a priority queue, you can extend this abstract class and implement the factory method to instantiate the implementation you want to test.

179

Chapter 8

Start by declaring the test case with a few specific values to use and an instance member to hold the queue itself:

public abstract class AbstractPriorityQueueTestCase extends TestCase { private static final String VALUE_A = “A”;

private static final String VALUE_B = “B”; private static final String VALUE_C = “C”; private static final String VALUE_D = “D”;

private static final String VALUE_E = “E”;

private Queue _queue;

...

}

Next, you define the setUp() and tearDown() methods. setUp() calls the abstract factory method createQueue() that follows. This is the method that each specific test needs to implement:

protected void setUp() throws Exception { super.setUp();

_queue = createQueue(NaturalComparator.INSTANCE);

}

protected void tearDown() throws Exception { _queue = null;

super.tearDown();

}

protected abstract Queue createQueue(Comparator comparable);

The first test establishes the behavior of an empty queue. This is exactly the same test shown in Chapter 4 for testing other types of queues. You could have avoided duplicating this code by having a more complex hierarchy of test cases, but we opted for simplicity and clarity. We do not recommend making this choice in production code!

public void testAccessAnEmptyQueue() { assertEquals(0, _queue.size()); assertTrue(_queue.isEmpty());

try { _queue.dequeue(); fail();

}catch (EmptyQueueException e) {

//expected

}

}

180

Priority Queues

The next method is the major test of your priority queue behavior. You begin by adding three items to the queue and making sure that the size() and isEmpty() methods are working as expected:

public void testEnqueueDequeue() { _queue.enqueue(VALUE_B); _queue.enqueue(VALUE_D); _queue.enqueue(VALUE_A);

assertEquals(3, _queue.size()); assertFalse(_queue.isEmpty());

Next, you make sure that the largest of the three items you added (in this case, the string D) is returned from the dequeue() method. In the preceding code that adds the items to the queue, this was the second of the three items, so a normal FIFO queue or LIFO stack fails this test straightaway. Having removed the item, you again verify that the other operations are still making sense:

assertSame(VALUE_D, _queue.dequeue()); assertEquals(2, _queue.size()); assertFalse(_queue.isEmpty());

The string B is the largest of the two remaining items, so you make sure that it is returned from the next call to the dequeue() method:

assertSame(VALUE_B, _queue.dequeue()); assertEquals(1, _queue.size()); assertFalse(_queue.isEmpty());

Add a couple more items to the queue. It is common in applications that use priority queues to have a mixture of enqueue() and dequeue() invocations, rather than simply building and then emptying the queue:

_queue.enqueue(VALUE_E); _queue.enqueue(VALUE_C);

assertEquals(3, _queue.size()); assertFalse(_queue.isEmpty());

You now have three elements in your priority queue: the strings A, E, and C. They should come off the queue in order from largest to smallest, so your test completes by removing each one of them in turn, while also ensuring that size() and isEmpty() remain consistent with your expectations:

assertSame(VALUE_E, _queue.dequeue()); assertEquals(2, _queue.size()); assertFalse(_queue.isEmpty());

assertSame(VALUE_C, _queue.dequeue()); assertEquals(1, _queue.size());

assertFalse(_queue.isEmpty());

assertSame(VALUE_A, _queue.dequeue()); assertEquals(0, _queue.size()); assertTrue(_queue.isEmpty());

}

181

Chapter 8

You complete the test case with another generic queue test to verify the behavior of the clear() method, as shown here:

public void testClear() { _queue.enqueue(VALUE_A); _queue.enqueue(VALUE_B); _queue.enqueue(VALUE_C);

assertFalse(_queue.isEmpty());

_queue.clear();

assertTrue(_queue.isEmpty());

}

That’s it for our general priority queue test. You can now move on to the first implementation, a very simple list-based queue that searches for the largest item when required.

Understanding the Unsorted List Priority Queue

The simplest way to implement a priority queue is to keep all of the elements in some sort of collection and search through them for the largest item whenever dequeue() is called. Obviously, any algorithm that uses a brute force search through every item is going to be O(N) for this operation, but depending on your application, this may be acceptable. If, for example, there are not many calls to dequeue() in your case, then the simple solution might be the best. This implementation will be O(1) for enqueue(), which is hard to beat.

In the next Try It Out, you implement a simple priority queue that holds the queued items in a list.

Try It Out

Testing and Implementing an Unsorted List Priority Queue

You use a LinkedList in this case, but an ArrayList would also work, of course.

Begin by extending the AbstractPriorityQueueTestCase you created previously and implementing the createQueue() method to instantiate your (not yet created) implementation:

public class UnsortedListPriorityQueueTest extends AbstractPriorityQueueTestCase { protected Queue createQueue(Comparator comparator) {

return new UnsortedListPriorityQueue(comparator);

}

}

This implementation has a lot in common with the other queue implementations you saw in Chapter 4. We have chosen to reproduce the code in common here for simplicity.

182

Priority Queues

Start by creating the class and declaring its two instance members: a list to hold the items and a Comparator to determine the relative size of the items. Also declare a constructor to set everything up:

public class UnsortedListPriorityQueue implements Queue { private final List _list;

private final Comparator _comparator;

public UnsortedListPriorityQueue(Comparator comparator) { assert comparator != null : “comparator cannot be null”; _comparator = comparator;

_list = new LinkedList();

}

...

}

The implementation of enqueue() could not be simpler; you just add the item to the end of the list:

public void enqueue(Object value) { _list.add(value);

}

You implement dequeue() by first verifying that the queue is not empty. You throw an exception if this method is called when the queue is empty. If there is at least one item in the queue, you remove the largest item by its index, as determined by the getIndexOfLargestElement() method:

public Object dequeue() throws EmptyQueueException { if (isEmpty()) {

throw new EmptyQueueException();

}

return _list.delete(getIndexOfLargestElement());

}

To find the index of the largest item in your list, you have to scan the entire list, keeping track of the index of the largest item as you go. By the way, the following method would be much better suited to an ArrayList than our chosen LinkedList. Can you see why?

private int getIndexOfLargestElement() { int result = 0;

for (int i = 1; i < _list.size(); ++i) {

if (_comparator.compare(_list.get(i), _list.get(result)) > 0) { result = i;

}

}

return result;

}

183