Priority Queues
(Sect. 6.1-6.3.3)One place a priority queue is seen is in the emergency room of a hospital. Generally we think of queues as first-come-first-serve (FIFO). But, that model is not always appropriate. If you go to the ER with a broken arm, and right behind you someone comes in with a gunshot wound, you are going to have to wait to be treated. Similarly, if someone went to the ER with a cold, your broken arm would probably be treated first. So, a gunshot would might have priority 2, a broken arm might have priority 5, and a cold might have priority 7. This is the idea behind a priority queue.
A computer science application of this is a printer queue. Often, if there is a 100-page job sent to the printer immediately followed by several 1-page jobs, the printer will complete the 1-page jobs first. (Not all printer queues do this, unfortunately!)
1. Name 2 other real-world examples of a priority queue.
2. Name at least 2 other places in computer science a priority queue would be used.
Often in computer science (although this is not always the case), items with lower numbers have the highest priority. That is the convention we will use here. (In other words, the "#1 priority" has value 1.)
Priority queues are an ADT. The operations usually defined are insert and deleteMin. The insert is equivalent to enqueue and deleteMin is equivalent to dequeue in a regular queue.
3. The most obvious way to implement a priority queue is using a linked list. Using this implementation:
a. What is the run-time for insert()?
b. What is the run-time for deleteMin()?
4. A modification of this approach is to make the linked-list sorted (by an item's priority). Using this implementation:
a. What is the run-time for insert()?
b. What is the run-time for deleteMin()?
5. Which is the better implementation, #3 or #4? Why?
A BST could also be used and would support insert and deleteMin on average in O(lg n). [Look in your book if you want to know why.] However, a BST supports many different operations that are not generally used, and as you now know, implementing a BST is not extremely simple. J
A common implementation of a priority queue is done using a binary heap. It will support insert and deleteMin in O(lg n) worst case. In addition, it is a straightforward implementation that doesn't involve pointers.
A heap is a binary tree that is completely filled, except perhaps on the bottom level, which must be filled from left to right. This is called a complete binary tree. (Sound familiar??)
6. Draw a complete binary tree of height 3.
7. To make it more general, a tree with height h has between _________ and __________ nodes.
This means the height of a complete binary tree is always O(lg N). Heaps are often represented
using trees, but they are actually implemented using arrays.
For example, consider the following heap and its implementation:
(This should look very familiar!)
(Don't worry about arr[0] yet.)
So, any element in array position i, the left child is in position 2i, and the right child
immediately follows the left child. The parent is in position i/2 (round down). This representation
allows many tree representations to be done quickly.
8. There is an obvious problem with this implementation. What is it?
In addition to being a complete tree, a heap also has another property. Since the minimum
element is the one that always needs to be removed, the minimum element is placed at the root.
In addition, every subtree should also be a heap. For any node N, the priority (also called the
key) of the parent of N is less than or equal to the key in N (except for the root, which has no
parent)
Ex. 1 Ex. 2
To summarize, a heap has two properties:
The heap-order property allows findMin in constant time.
9. Describe a general algorithm for insert(). (Don't write code here, just a general approach.) Draw a diagram showing a heap and several insertions to illustrate your algorithm.
10. Repeat #9 for deleteMin.
11. Can you think of any implementation reason arr[0] is left blank?