[ Data Structures with Java ] Section 15.4 : Priority Queues

Preface :
A queue is a data structure that provides FIFO ordering of elements. Access is limited only to the first of "oldest" element in the queue and a deletion operation removes this element. Applications sometimes require a modified version of a queue in which access is given to the element with a priority ranking instead of chronological order. This structure, called a priority queue, removes the element of highest priority. The ranking of the elements in a priority queue is determined by some external criterion. For instance, suppose a business provides a centralized office pool to handle a variety of jobs for the staff. Company policy judges job requests by the president to be of highest priority (Priority 3), followed by requests from directors (Priority 2), from managers (Priority 1), and finally from clerks (Priority 0). A person's rank in the company becomes a criterion that measures the relative importance of a job. Instead of handling jobs on a first-come/first-served basic, the office pool uses a priority queue to handle jobs in the order of their assigned importance. For instance, below figure shows jobs 1-4 in the priority queue. The office pool processes the jobs in the order #2, #1, #4 and #3 so that the president is handled first and the clerk is handled last.


The "bucket" display in upper figure is a good abstract model for a priority queue. There is no assumption on how elements enter the priority queue but only a criterion for their exit. Think of a priority queue as a collection of elements loosely tossed into a bucket. Removing an element involves reaching around in the bucket and pulling out the one with the highest priority.
In a maximum priority queue, the highest-priority item has the largest value. The secretarial pool example illustrate a maximum priority queue. In a minimum priority queue, the highest-priority item has the smallest value. As an example of a minimum priority queue, an operating system can insert print jobs into a priority queue on the basic of the number of pages. In this situation, the higher-priority jobs are those with the lower page count. It is reasonable to print 2-,7- and 10- pages before a 100-page job.

A Simple Priority Queue Implementation :
Below is a simple example of using OrderedList to be the underlying data structure of the Priority queue. So the elements in the Priority queue should implements the Comparable interface for further operations.
The collection OrderedPQueue implements the PQueue interface which uses the same method names found in the Stack and Queue interfaces. So each time you add element into the OrderedPQueue, the new element will be insert into correct location to make sure the underlying data structure is in order. So we pop the element will have the highest priority among elements in the data structure (Bucket) :

- OrderedPQueue.java : Simple implementation of Priority Queue

view plaincopy to clipboardprint?

1. package DSwJ.S15;  
2.   
3. import DSwJ.S12.OrderedList;  
4.   
5. public class OrderedPQueue extends Comparablesuper T>> implements PQueue{  
6.     private OrderedList orderList=null;  
7.       
8.     public OrderedPQueue(){orderList = new OrderedList(OrderedList.DESCENDING);}  
9.   
10.     @Override  
11.     public boolean isEmpty() {  
12.         return orderList.isEmpty();  
13.     }  
14.   
15.     @Override  
16.     public T peek() {  
17.         return orderList.peek();  
18.     }  
19.   
20.     @Override  
21.     public T pop() {  
22.         return orderList.removeFirst();  
23.     }  
24.   
25.     @Override  
26.     public void push(T item) {  
27.         orderList.add(item);          
28.     }  
29.   
30.     @Override  
31.     public int size() {  
32.         return orderList.size();  
33.     }  
34.       
35.     public static void main(String args[]){  
36.         HeapPQueue pq = new HeapPQueue();  
37.         pq.push("green");  
38.         pq.push("red");  
39.         pq.push("blue");  
40.         System.out.println(pq.size()+" "+pq.peek());  
41.         while(!pq.isEmpty()) System.out.print(pq.pop()+" ");  
42.     }  
43. }  

Output:
3 red
red green blue

This message was edited 1 time. Last update was at 11/10/2010 17:18:55