Previous Section
 < Free Open Study > 
Next Section

9.1 ADT Priority Queue

A priority queue is an abstract data type with an interesting accessing protocol: Only the highest-priority element can be accessed. "Highest priority" can mean different things, depending on the application. Consider, for example, a small company with one secretary. When the other employees leave work on the secretary's desk, which jobs are done first? The jobs are processed in order of the employee's importance in the company; the secretary completes the president's work before starting the vice-president's job, and does the marketing director's work before staff programmers' tasks. The priority of each job relates to the level of the employee who initiated it.

In a telephone answering system, calls are answered in the order in which they are received; that is, the highest-priority call is the one that has been waiting the longest. Thus a FIFO queue can be considered a priority queue whose highest-priority element is the one that has been queued the longest time.

Logical Level

As you would expect, the Priority Queue ADT has exactly the same operations as a FIFO queue. The only difference relates to the postcondition of the Dequeue operation. Thus, we do not need to use a CRC card and can go directly to the specification.

Application Level

In discussing FIFO queue applications in Chapter 4, we said that the operating system of a multiuser computer system may use job queues to save user requests in the order in which they are made. Such requests might also be handled according to the importance of the job request. That is, the head of the company might get higher priority than the junior programmer. An interactive program might get higher priority than a job to print out a report that isn't needed until the next day. To handle these requests efficiently, the operating system may use a priority queue.

Hospital emergency rooms see patients in priority queue order; the patient with the most severe injuries sees the doctor first. Graduating seniors go to the head of the waiting list (priority queue) when trying to register for classes that are full. See Figure 9.1.

Click To expand
Figure 9.1: Real-life priority queue

Priority queues are also useful in sorting. Given a set of elements to sort, we can enqueue the elements into a priority queue, and then dequeue them in sorted order (from largest to smallest). We look more closely at how priority queues can be used in sorting in Chapter 10.

Implementation Level

There are many ways to implement a priority queue. In any implementation, we want to access the element with the highest priority quickly and easily. Let's briefly consider some possible approaches:

Unsorted List Enqueuing an item would be very easy-simply insert it at the end of the list. Dequeuing would require searching through the entire list to find the item with the highest priority.

Array-Based Sorted List Dequeuing is very easy with this approach-simply return the item with the highest priority, which would be in the length - 1 position (provided the array is kept in increasing order of priority). Thus, dequeuing is an O(1) operation. Enqueuing, however, would be more expensive. We have to find the place to enqueue the item-O(log2N) if we use a binary search-and rearrange the elements of the list after inserting the new item-O(N).

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

Binary Search Tree For this approach, the Enqueue operation would be implemented as a standard binary search tree Insert operation. We know that it requires O(log2N) steps on average. Assuming we have access to the underlying data structure of the tree, we can implement the Dequeue operation by returning the rightmost tree element. We follow the right subtree down, maintaining a trailing pointer as we go, until we reach a node with an empty right subtree. The trailing reference allows us to "unlink" the node from the tree. We then return the node. This is also an O(log2N) operation on average.

Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)