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, the convention that will be followed is that the smallest value has the highest priority.
- 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 ('first in, first out') 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, the level of frustration experienced by the users is reduced. In fact, it can be shown that printing documents in order of their length minimizes the average time a user waits for a document.
-
We can use a tree structure to keep track of the items in a priority queue - 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 or other life-critical systems.
-
There is a structure that will provide guaranteed O(log n) performance for both insertion and deletion: it's called a heap.
