Skip to main content
Lesson 41 - Priority Queues
ZIPPDF (letter)
Lesson MenuPreviousNext
  
Priority Queues page 3 of 9

  1. Often the items added to a queue have a priority associated with them: this priority determines the order in which they exit the queue - highest priority items are removed first. In this curriculum guide, we will follow the convention that the smallest value has the highest priority.

  2. For example, consider the software that manages a printer. In general, it is possible for users to submit documents for printing much more quickly than it is possible to print them. A simple solution is to place the documents in a FIFO queue. In a sense this is fair, because the documents are printed on a first-come, first-served basis.

    However, a user who has submitted a short document for printing will experience a long delay when much longer documents are already in the queue. An alternative solution is to use a priority queue in which the shorter a document, the higher its priority. By printing the shortest documents first, we reduce the level of frustration experienced by the users. In fact, it can be shown that printing documents in order of their length minimizes the average time a user waits for her document.

  3. As we have seen, we could use a tree structure - which generally provides O(log n) performance for both insertion and deletion. Unfortunately, if the tree becomes unbalanced, performance will degrade to O(n) in worst cases. This will probably not be acceptable when dealing with dangerous industrial processes, nuclear reactors, flight control systems and other life-critical systems.

  4. There is a structure that will provide guaranteed O(log n) performance for both insertion and deletion: it's called a heap.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.