In concept, a priority queue is a queue in which information is inserted and in which stored information is removed. It differs from a standard queue in that each unit of information has a "priority" number attached to it, and the information is removed according to its priority number. The element with the highest priority (usually the lowest priority number) is removed before other information in the queue even though it may have been in the queue for a shorter period of time than other elements.
For example, suppose elements with priority values of 20, 40, 50 and 15 are inserted into a priority queue in this order. The element with priority value of 15 would be removed first even though it was the last element inserted into the queue.
Priority queues could be used to model situations where the priority value may be associated with the importance of the data (e.g., in emergency rooms, heart attacks are treated before broken arms, which are treated before insomnia), or rank of the person submitting the data (e.g., the president of a company gets his or her projects done before any vice-president who gets projects done before any branch manager).
As with other ADTs, priority queues can be implemented in several ways. Each way presents its own set of questions and issues for resolution before actual coding of operations begins.
If this choice is made, the major questions which need resolution are (1) how should data be stored in the queue, (2) how to insert data into the queue, and (3) how to delete data from the queue.
We address these questions in order:
(index) 0 1 2 3 4 5 6
____________________________________
| 20 | 40 | 50 | 15 | | | |
|____|____|____|____|____|____|____|
let us first insert 60 into the queue. The variable count
has the value of 5 and we now have this state
of the priority queue:
(index) 0 1 2 3 4 5 6
____________________________________
| 20 | 40 | 50 | 15 | 60 | | |
|____|____|____|____|____|____|____|
We want to identify 15 as the minimum element and dequeue it.
This basically means performing a linear search, starting at
index 0 and going through the end (index 4, which is the value of count-1).
But we cannot merely take 15 (at location 3) out of the array and leave a "hole" there!
To avoid the "hole" we take the LAST ELEMENT (at location count-1) and place it in location of the minimum element (i.e., at index 3), and then decrement the value of count by one.
Thus, the priority queue now looks like:
(index) 0 1 2 3 4 5 6
____________________________________
| 20 | 40 | 50 | 60 | | | |
|____|____|____|____|____|____|____|
Note the following implications: (1) At any state of the queue we
have no idea of the relationship of the elements in the queue with
the order in which they were inserted into the queue. (2) Also, each
deletion means that the last element will be moved to "plug a hole" left
by the deleted element, but no other elements in the queue will
be moved.
If we perform another deletion, the element 20 will be removed and the priority queue will look like:
(index) 0 1 2 3 4 5 6
____________________________________
| 60 | 40 | 50 | | | | |
|____|____|____|____|____|____|____|
Detailed code for this deletion function may be found in Ford and Topp, pg 226.
If this choice is made, we need to answer the same questions as before, namely: (1) how should data be stored in the queue, (2) how to insert data into the queue, and (3) how to delete data from the queue.
We address these questions in order:
Assume we are inserting 14 into the following priority queue (as a "minimum-root" heap).
13
/ \
/ \
21 16
/ \ / \
24 31 19 68
/\ /
65 26 32
Note that in this tree, every node is smaller than its children, which
makes the structure properly a heap (with root being the minimum).
The new element would go at the end of the array, which means it would
follow 32 in the array and be construed as the right child of 31.
13
/ \
/ \
21 16
/ \ / \
24 31 19 68
/\ /\
65 26 32 14
The insertion function must compare 14 with its parent (31) and exchange it if necessary (i.e., if it is smaller than 31). Since the original tree was a heap, 31 must have been smaller than its child (32), and if 31 is replaced with something smaller (14), this will be smaller than the original child and so no comparison need be made with that child. A comparison must be made with the parent (i.e., 21) and another exchange made if necessary. This is continued until the inserted value (14) is less than a parent. We end up with the following tree.
13
/ \
/ \
14 16
/ \ / \
24 21 19 68
/\ /\
65 26 32 31
At most, this will require log2n comparisons and
exchanges, which is decidedly faster than n comparisons.
This insertion function, although taking more steps than the insertion used in the linear array priority queue, prepares the data structure for easy identification of the next item to be removed, since it must be at the root (i.e., first location in the array).
To delete an item from the queue, we remove it from the root of the heap (i.e., first location in the array), and then readjust the heap to eliminate the "hole."
The readjustment can take several forms. One way is as follows.
As with heapsort, we take the last leaf and move it to take the place of the root (we can alternatively keep it in a temporary location to be used for comparison until its final insertion in the correction location).
Pick the smaller of the two children of the root, compare it with new value in the root (or the value in the temporary location) and move it up a generation if it is less than what is in the root (temporary location).
This process is repeated until either (1) one has moved up a leaf to take the place of its parent (and then the old last leaf value [in the temporary location] takes the place of this other leaf), or (2) the old last leaf value is greater than some value, but less than its parent, and is placed at that location in the tree.
For example, using a slightly different tree than used above (we substitute 19 for 24) and removing the root, we have
__
/ \
/ \
14 16
/ \ / \
19 21 19 68
/\ /\
65 26 32 31
We take the last leaf (31) and move it to the root. Then we determine
the lesser of the two children of the root (14) and
replace the root by 14, and 14 by 19, and finally, 19 by 26. All of these
values are smaller than the value of the last leaf (31). Thus we
have
14
/ \
/ \
19 16
/ \ / \
26 21 19 68
/\ /
65 __ 32
The value in the former last leaf (31) is inserted into the remaining
"hole" in the tree at the location of a leaf and we have the
following tree.
14
/ \
/ \
19 16
/ \ / \
26 21 19 68
/\ /
65 31 32
If, however, the initial queue (heap) was
13
/ \
/ \
14 16
/ \ / \
19 21 19 68
/\ /\
65 26 32 22
(with 22 instead of 31 as the last leaf)
dequeing an element (i.e., 13), would result in the revised queue
looking like
14
/ \
/ \
19 16
/ \ / \
22 21 19 68
/\ /
65 26 32
In other words, 22 does not percolate down to being a leaf, but, rather,
halts as the left child of 19 and the parent of 65 and 26.
For n large, this is a significantly quicker approach than the linear array approach.
This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 2000 Dennis C. Smolarski, SJ, All rights
reserved.
Last changed: 4 March 2000.