$ mkdir ~/cs170/labs/lab22 $ cd ~/cs170/labs/lab22
I've graded your post lab 20, and you will find your grade online. There seemed to be a fair amount of confusion going on, with how operated with these pieces of code. We'll go over exercise 4 and 5 today, to make sure everyone understands what is going on.
We've used Queues and Stacks over the past week or so, to shed some light on how data structures can change the behavior of an algorithm considerably. Today, we'll look at one new data structure: Priority Queues. Priority Queues have great applications in all sorts of algorithms, as we will see over the course of the rest of the semester.
A Priority Queue is a more generalized form of a queue. For a normal queue, items are inserted into the queue at the end. This is essentially inserting items into the queue specified by time. For a priority queue, we can specify a priority value to dictate where it should appear in the queue.
In a file called priority_queue.py, create a class
called PriorityQueue. Notice that I am not making you
copy your linked list into this directory; You are going to
implement PriorityQueue using a Python list. You must implement
the following methods:
insert(self, data, priority). This function takes
two parameters: some data, and an integer priority. It should
insert a tuple representing the data and its priority into
the queue.
dequeue(self). This function
removes (and returns!) the data of the element
with the smallest priority from the queue.
peek(self). This function returns the data from the
minimum element of the priority queue, without removing it.
update_priority(self, data, new_priority). This
function takes some data, and an integer
for new_priority. It should remove the old tuple for
data, and insert the new tuple.
Make sure that your methods work appropriately!
>>> pq = PriorityQueue()
>>> pq.insert(1, 0)
>>> pq.insert(2, 1)
>>> pq.insert(4, 3)
>>> pq.insert(3, 2)
>>> print(pq)
[(1, 0), (2, 1), (3, 2), (4, 3)]
>>> print(pq.dequeue())
1
>>> print(pq.dequeue())
2
>>> print(pq)
[(3, 2), (4, 3)]
>>> pq.insert("Hello", 0)
>>> pq.insert("World", -1)
>>> print(pq)
[("World", -1), ("Hello", 0), (3, 2), (4, 3)]
>>> pq.update_priority("World", 1)
>>> print(pq)
[("Hello", 0), ("World", 1), (3, 2), (4, 3)]
You can create tuples by separating their values using a comma. You will need to perform this in your insert procedure, so you can insert the tuple into the queue.
Your insert method will look a lot like the insert
procedure for insertion sort. You need to slide things down
in the list to make room for the element you want to add. Be
careful though! You need to make room for the element first.
Append None to the end of the list first, so you
don't accidentally go out of the range of the list!
update_priority could just resort the list.
However, we are just going to delete the element with that
data, and re-insert into the list at the correct spot.
If you have done the above correctly, your list will always
be in sorted order. This is good, because it makes writing
dequeue and peek very easy. Just
access (and/or remove) the element at index 0!
Part of the reason we are using a Python list today is to make the construction of the object a little bit easier. However, it does slightly make writing the insert procedure of the list more difficult. Inserting into sorted order using a linked list is surprisingly easy.
Make a class called PriorityQueueList, which uses a
linked list to store the priority queue!
When you have finished, create a tar file of your lab22 directory. To create a tar file, execute the
following commands:
cd ~/cs170/labs tar czvf lab22.tgz lab22/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
22. Make sure you include a header
listing the authors of the file.