## Lecture 22 - Priority Queues

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab22$ cd ~/cs170/labs/lab22


### Queue Tracing

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 queues operated with these pieces of code. We'll go over exercise 4 and 5 today, to make sure everyone understands what is going on.

### Priority Queue

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.

Lab Activity 1
Priority Queues

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.

#### Details

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!

#### Example

>>> 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)]


#### Hint

• 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!

### Challenge

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!

#### Submission

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.