Prev: Binary Search Trees
- by Brad Bart, Simon Fraser University
- Elementary Data Structures
- Linked Structures 1: Binary Search Trees
- Linked Structures 2: Binary Heaps
Priority Queues
A priority queue is like a regular queue in that it is a collection of keys which you may insert and remove, except that each key has a priority number associated with it: the lower the number, the higher the priority. The key with the highest priority is the next key to be removed.
If you're having a tough time envisioning what's happening here, think of the following examples.
Your chores list. Chores seem to be the work that never ends: when you finish a chore, you'll have to do it again a day or a week or a month from now. And certainly some chores are more palatable than others. Perhaps you prefer vacuuming the carpets, cleaning the toilets and washing the car, versus hanging the laundry, washing the dishes or ironing your shirts. If you are like most people, your tendency would be to pick first the chore(s) you prefer the most, therefore, the priority queue of chores is ordered starting from the chore which is the least unpalatable.
Your “To do” list. This is much like the first example, but extended to all the activities in your life. But unlike the first example, the queue is unlikely to ever be empty because, for most people, there aren't enough hours in the day to get done everything that they would like. So they prioritize, and defer the items of lowest priority.
People you want to date. I'll let you fill in the details on this one.
Case Study: Priority Queue Implementation Using an Array
|
Again, let
n
represent the current size, i.e., the number of keys the priority queue
currently holds.
In all implementations, the keys will be contained
within the first n array elements, i.e., |
Again, there are two “obvious” approaches:
Store the keys in the first n slots of the array,
in reverse-sorted order.Store the keys in the first n slots of the array,
in any order.
Once again, you should pause to think about how you would implement insert and remove using each of these data structures. Also consider the efficiency of each operation.
Once you have formed your answers, proceed to the implementation below.
Implementation 1: Keys are stored in reverse-sorted order
To insert is similar to the insert operation for a dynamic set using a sorted array: to keep the list in reverse order may require up to O(n) shifts. However, to remove the minimum would require no shifting (i.e., O(1)) because the minimum must be the last element of the array.
void insert(int key, int priority) {
// shift all A[] < priority
int j = len-1;
while (j >= 0 && A[j].priority < priority) {
A[j+1] = A[j];
j--;
}
A[j+1] = Node(key, priority);
len++;
}
int remove() {
return A[--len].key;
}
Implementation 2: Keys are stored in any order
In contrast with Implementation 1, this data structure has the opposite efficiency, i.e., there is a fast O(1) insert, but a slow O(n) remove. To insert, place the new key into the first unoccupied slot, just like for a dynamic set using an un-sorted array. To remove requires a linear search to locate the minimum.
void insert(int key, int priority) {
A[len++] = Node(key, priority);
}
int remove() {
// linear search for position of minimum
int smallest = A[0].priority;
int smallestpos = 0;
for (int pos = 1; pos < len; pos++)
if (A[pos].priority < smallest.priority) {
smallest = A[pos].priority;
smallestpos = pos;
}
int ret = A[pos].key;
A[pos] = A[--len];
return ret;
}
Augmentation to Implementation 2: Indexing the minimum
Consider what would happen if your algorithm maintained
the array index of the minimum. In other words, use a
variable minpos such that A[minpos]
is always the current minimum of the priority queue.
How would that change insert
and remove?
It would certainly make a lot of things easier. For starters, remove would no longer have to a O(n) linear search to locate the minimum.
But can the location of the minimum be easily updated
after an insert? No problem. If you add one new element
to a set, it's either smaller than the old minimum, in
which case you update minpos, or it's not,
in which case minpos doesn't change.
Therefore, by this simple augmentation, both insert and remove will run in O(1) operations.
There is a flaw in this plan and it's worth it for you to figure it out for yourself. And that means some thinking time on your own.
Yes, the answer is in the next part, but you should really [seriously] resist the temptation to open the next page until you've thought it through. And I don't mean for something lame like 30 seconds! Or even 30 minutes! You don't want problems like this to pwn you.
After you're convinced why the improved O(1) running times are a mirage, come back tomorrow to read the final instalment.
Next: Tomorrow's Reading: The Final Instalment