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

1 import java.util.PriorityQueue;
2
3 public class PriorityQueueDemo
4 {
5 public static <AnyType extends Comparable<? super AnyType>>
6 void dumpPQ( String msg, PriorityQueue<AnyType> pq )
7 {
8 System.out.println( msg + ":" );
9 while( !pq.isEmpty( ) )
10 System.out.println( pq.remove( ) );
11 }
12
13 // Do some inserts and removes (done in dumpPQ).
14 public static void main( String [ ] args )
15 {
16 PriorityQueue<Integer> minPQ = new PriorityQueue<Integer>( );
17
18 minPQ.add( 4 );
19 minPQ.add( 3 );
20 minPQ.add( 5 );
21
22 dumpPQ( "minPQ", minPQ );
23 }
24 }

figure 6.41
A routine to
demonstrate the
PriorityQueue

that the library designers did not choose to make PriorityQueue an interface.
Nonetheless, the PriorityQueue implementation in Java 5 is sufficient for most
priority queue applications.

An important application of the priority queue is event-driven simulation . Con-
sider, for example, a system such as a bank in which customers arrive and wait in
line until one of K tellers is available. Customer arrival is governed by a probability
distribution function, as is the service time (the amount of time it takes a teller to
provide complete service to one customer). We are interested in statistics such as
how long on average a customer has to wait or how long a line might be.
With certain probability distributions and values of K , we can compute
these statistics exactly. However, as K gets larger, the analysis becomes
considerably more difficult, so the use of a computer to simulate the operation
of the bank is appealing. In this way, the bank's officers can determine how
many tellers are needed to ensure reasonably smooth service. An event-driven
simulation consists of processing events. The two events here are (1) a cus-
tomer arriving and (2) a customer departing, thus freeing up a teller. At any
point we have a collection of events waiting to happen. To run the simulation,
we need to determine the next event; this is the event whose time of occur-
rence is minimum. Hence, we use a priority queue that extracts the event of
minimum time to process the event list efficiently. We present a complete dis-
cussion and implementation of event-driven simulation in Section 13.2.

An important use
of priority queues
is event-driven
simulation .