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:
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.
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.
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.
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)
Data Structures | |||
---|---|---|---|
Sorted list | |||
Unsorted list | |||
Balanced search tree^{(1)} | |||
Heap | easy to implement | ||
Tournament tree | see next section |
Fig. 3.1 Location of minimum element in a binary search tree.
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
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.
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 log_{2} n element comparisons.
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 log_{2} 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.
This may cause problems when the inserted element has to start a new bottom level. Every time the number of nodes goes from 2^{k} to 2^{k}+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 2^{k} and 2^{k}+1. Can you suggest a solution that makes INSERT/DELETE work in O(log n) time in the long run?
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:
Here is the Java code: qu1.java
On Tournament Trees :
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 :