< Back

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.


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:

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())
>>> print(pq.dequeue())
>>> 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.