## Topic #15: Priority queues: overview and applications

### Priority Queue A.D.T.

A priority queue is a data structure for maintaining a set of elements, each with an associated value called a key. The basic model of this Abstract Data Type consists of the following operations:

• MAKENULL
• INSERT
• DELETE_MIN

Note that DELETE_MIN could also be replaced by DELETE_MAX, by reversing the linear order of the priority queue. Thus, a priority queue can be used to find either a minimum or a maximum, but this needs to be known a priori.

Of course, as with any mathematical model set, it is possible to add other operations, but these would not be part of the basic model.

### Uses of Priority Queues

1. Discrete Event Simulation

Discrete event simulation is concerned with processes and systems that change at discrete instants. For example, pushing an elevator button, starting of a motor, stopping of a motor, and turning on a light, are all discrete events because there is an instant of time at which each occurs. Activities such as moving a train from point A to point B are not discrete events because they have a time duration. However, we can model an event like this as two separate discrete events: the event of the train leaving point A, and the event of the train arriving at point B. If we associate a time value with each discrete event,then we can model the duration activities as the difference between the times associated with the events marking the beginning and the end of each activity. For example, we can specify that the arrival at point B occurs 3 hours and 37 minutes after leaving point A. Therefore, we can see that if the train leaves point A at 7:53pm, then it will arrives at point B at 11:30pm.

The purpose of a discrete event simulation is to study a complex system by computing the times that would be associated with real events in a real-life situation. In the train example above, suppose that we know that when the train arrives at point B, a load is transferred to a second train that arrives at point C after 45 minutes. That is, the second train's departure from point B is triggered by the first train's arrival, and the arrival at point C occurs with a delay of 45 minutes after the departure from point B. In this simple example, we can use discrete event simulation to determine that the second train will arrive at point C at 12:15am.

Use priority queues to build the Future Event Set. After computing an event, all we need to do is INSERT() it into our data structure. The next event can be extracted easily with the operation DELETE_MIN.

Fig. 1.1 A future Event Set

For any furhter information on this subject, please refer to topic #17 of the lecture notes.

2. Operating System Scheduling

An operating system is a program that manages, among other things, the usage of the CPU in an environment with many processes (multi-user, multi-tasking, UNIX, etc.). Each process can only be executed for a short amount of time, after which, if its time limit is up without having terminated its task, the process will be placed on the queue again. A good implementation for this type of queue would be a priority queue, to optimize the overall processing time of jobs. The priority could be set de pending on how long the process has been waiting (to avoid starvation), and could also depend on who started the process (e.g. a process started by the root would have higher priority than a process started by a user).

Fig. 2.1 Operating system using a priority queue method.

Fig. 2.2 Operating system using the Round Robin method.

3. Sorting

Priority queues can also be used to sort in a very efficient manner.

Here is a generic sorting algorithm:

```for all input items x do :
insert(x, priority queue);
while NOT EMPTY(priority queue) do
output deletemin (priority queue);
(* they come out in order *)

```

Note how this algorithm is very short (4 lines), thus easy to remember, as well as very efficient, since it can sort in worst-case (n log n). (see next topic on heaps for more information)

### Overview of priority queue implementations

Data Structures
INSERT
DELETE_MIN
TOTAL
Sorted list
(n)
(1)
(n)
Unsorted list
(1)
(n)
n)
Balanced search tree(1)
(log n)
(log n)
(log n)
Heap
(log n)
log (n)
(log n)
easy to implement
Tournament tree
(log n)
log (n)
(log n)
see next section
(1) Assuming height of tree is O(log n), min will be at bottom left corner:

Fig. 3.1 Location of minimum element in a binary search tree.

### Tournament Trees

A tournament tree is a binary tree in which we store all nodes flush at the bottom level of a complete binary tree. If the number of nodes n is not a power of 2, then the tree is padded with "infinity" nodes on the right.

If n is a power of 2, there are n-1 internal nodes, 2n-1 total nodes, and n-1 edges.

The key value of an internal node is the minimum of its two children. This way the root has the minimal value, as in a heap.

Here is an example of a tournament tree :

Notice how this tree is a complete binary tree, where elements get repeated. The root has the minimal value as in a heap. Tournament trees may be useful as priority queue implementations and for sorting.

Operations on tournament trees

• MAKETREE:

The tree is built from the bottom-up. That is, each input number is placed at the bottom, as a leaf. You need to make sure you have a number of leaves that is a power of 2 (if not, just add extra leaves with "infinity" as their key values). Then, pair the leaves up, and find the two leaves' parents, which is the minimum of the two.

Done in O(n) time.

• DELETE:

To delete an element, retrace the path down to its leaf (remember that elements repeat themselves), and replace the leaf with an "infinity" node. Then, simply replay!

Takes log2 n element comparisons.

• TOURNAMENT SORT:

Since the smallest element is found at the root, we can use this tree to sort. Thus, n elements can be sorted with only n log2 n comparisons, using the generic algorithm (MAKETREE followed by n DELETEs).

This method of sorting is called Tournament sort,with a worst case time of (n log n), which is very efficient.

• INSERT:

This may cause problems when the inserted element has to start a new bottom level. Every time the number of nodes goes from 2k to 2k+1, the time taken is O(n), while insertion at other points takes time O(log n). This is not very efficient: imagine what happens with a sequence of alternating INSERT/DELETE operations when n oscillates between 2k and 2k+1. Can you suggest a solution that makes INSERT/DELETE work in O(log n) time in the long run?

### Java Applet on Priority Queues

The Java Applet is an Animation of how one would Insert and Delete values of a priority queue. The button named Sorted loads up the Sorted method of insertion and deletion. The button named Unsorted loads up the Unsorted Slide show.

The Sorted Slide Show:
Animates that the work spent orginally , to add values in the proper order based on their priority allows a much easier deletion of these nodes after.

The Unsorted Slide Show:
Animates that if we do not take effort in placing the values in proper sorted order it becomes a big hassle and more effort is needed in order to delete nodes according to their higher priority.

As one can see from this applet the effort used in sorting the nodes initially leads to much easier and efficient deletions, where as unsorted algorithms take up much more time in order to delete them and reconstruct the new array.

Instructions for Applet:

1. Choose a BUTTON either SORTED or UNSORTED
2. Press Next to view slides
3. At end of Slide Show press Restart, in order to restart Slide Show.

### Links to related material

On Tournament Trees :

### References

• CORMEN, Thomas H. and LEISERSON, Charles E. and RIVEST, Ronald L., Introduction to Algorithms, The Massachusetts Institute of Technology, Cambridge, Massachusetts, 1990.
• WEISS, Mark Allen, Data Structure and Algorithm Analysis in C, The Benjamin/Cummings Publishing Company, Inc., Redwood City, California, 1993.
• Mathematical Symbol made by Amy Chow.

### Web page designers

This section is provided to give readers the opportunity to contact us, to point out errors or omissions, to ask questions, and to suggest improvements. Explanations on the role of each team member is included in the creation of the web page.

The creators are, in no particular order :

Last updated March 7, 1997 by Julie Anouk Mercier

Copyright © 1997, Karan Aulakh, Joni Clegg, Alice Gruber and Julie Anouk Mercier. All rights reserved. Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy. Disclaimer: this collection of notes is experimental, and does not serve as-is as a substitute for attendance in the actual class.