The collections api - Data Structures and Problem Solving Using Java - page 275

wait and thus seem to take a long time to run. Clearly, users who are running
an editor should not see a visible delay in the echoing of typed characters.
Thus short jobs (that is, those using fewer resources) should have precedence
over jobs that have already consumed large amounts of resources. Further-
more, some resource-intensive jobs, such as jobs run by the system adminis-
trator, might be important and should also have precedence.
If we give each job a number to measure its priority, then the smaller
number (pages printed, resources used) tends to indicate greater importance.
Thus we want to be able to access the smallest item in a collection of items
and remove it from the collection. To do so, we use the findMin and deleteMin
operations. The data structure that supports these operations is the priority
queue and supports access of the minimum item only. Figure 6.40 illustrates
the basic priority queue operations.
Although the priority queue is a fundamental data structure, before Java 5
there was no implementation of it in the Collections API. A SortedSet was not
sufficient because it is important for a priority queue to allow duplicate items.
In Java 5, the PriorityQueue is a class that implements the Queue interface.
Thus insert , findMin , and deleteMin are expressed via calls to add , element , and
remove . The PriorityQueue can be constructed either with no parameters, a com-
parator, or another compatible collection. Throughout the text, we often use the
terms insert , findMin , and deleteMin to describe the priority queue methods.
Figure 6.41 illustrates the use of the priority queue.

As the priority queue supports only the deleteMin and findMin operations,
we might expect performance that is a compromise between the constant-time
queue and the logarithmic time set. Indeed, this is the case. The basic priority
queue supports all operations in logarithmic worst-case time, uses only an
array, supports insertion in constant average time, is simple to implement, and
is known as a binary heap . This structure is one of the most elegant data struc-
tures known. In Chapter 21, we provide details on the implementation of the
binary heap. An alternate implementation that supports an additional
decreaseKey operation is the pairing heap , described in Chapter 23. Because
there are many efficient implementations of priority queues, it is unfortunate

The binary heap
implements the
priority queue in
logarithmic time
per operation with
little extra space.

figure 6.40
The priority queue
model: Only the
minimum element is
accessible.

deleteMin
findMin

insert

Priority
Queue