Implementing a Priority Queue

00:00 In the previous lesson, I wrapped up FIFI queues, talking about how to choose which library to use in your code. In this lesson, I’ll be introducing priority queues.

00:11 A priority queue is a queue that’s particular about how items inside of it are ordered. The ordering of the items in this kind of queue is based on priority, most important item first. As such, the queue is always sorted in priority order.

00:26 Inserting items into a priority queue is more expensive than a regular queue because the right spot in the order must be found. The most common use of a priority queue is inside of operating system schedulers. These schedulers ensure that high-priority tasks are scheduled before low-priority tasks. For example, you don’t want your screen to freeze up because a disk defragmentation is going on. Like with stacks and FIFO queues, you can use the built-in list type as a priority queue. Dequeuing an item is cheap, just use .pop() to get at the item. Enqueuing, on the other hand, is expensive—not only computationally, but also for the programmer.

01:08 One way of using a list as a priority queue is to manually sort the list. In this case, you can append a bunch of items in batch and then sort afterwards. You’re in control of the sort, so you can determine the timing.

01:22 Python’s .sort() method uses something called Timsort. This is O(n) execution with most lists, but O(n log n) in the worst-case scenario. Lists support sorting in reverse, and because they’re using the .sort() method, you can specify the key of the items in your list to use for sorting.

01:40 For example, if your objects in your list have a member named 'priority', you can specify that member be used when sorting the items. One of the drawbacks of this manual method is that it isn’t enforced.

01:53 If you forget to call the .sort() method on your list, it ceases to be in priority order. This can be an easy bug to miss if you’re changing the contents of your list-as-priority-queue throughout your code.

02:07 Let’s look at using a list as a priority queue. Here, I’m using tuples as the objects to prioritize. The first part of each tuple is a number indicating the priority.

02:18 The second part is the payload. To insert into the priority list queue, first append the list. Note, at this moment, it isn’t in priority order anymore. Now sorting it in reverse order makes it prioritized.

02:36 You can now use .pop() to get the highest-priority item out of the queue. Let’s do that again.

02:49 Still in priority order. Pretend for a moment that the first value in the tuple isn’t a priority number, but just some data. Let’s say the priority is based on the alphabetical order of the second part of the tuple. To do this, you need to tell .sort() what key in the object to use as the priority value.

03:11 Here, the lambda passed to .sort() indicates the item in position 1, the second spot, of the tuple is the sort key.

03:20 Looking at the result, and now it is by alphabetic order, with the 's' in 'sleep' being the highest value, therefore the object with the highest priority. Previously, I was using reverse, so I was using the smallest number to mean the highest priority. This time, I didn’t use reverse, so in this case, the value at the end of the alphabet has the highest priority.

03:45 You can see that using a list as a priority queue is possible, but it might be a little error-prone. If you forget one of these steps as you code, you could end up with a damaged priority list.

03:58 There’s another way of keeping your list as priority queue sorted, and that is the insort() function from the bisect library. The insort() function does an insert in sorted order.

04:10 insort() assumes that the list being operated on is already ordered. It is performant, in that it only takes O(log n) to find a spot for the new item, but you’re still inserting into a list.

04:24 Arbitrary insertion in a list is O(n), which tends to quickly outpace the value of the O(log n) search. Further, you’re restricted in that insort() doesn’t support reverse-sorting the list or have a way of specifying sort keys.

04:41 The final drawback is that there is no way of restricting insertion to just this method. You could forget in one spot in your code, use a regular .append(), and mess up the order of your list as priority queue.

04:55 To use insort(), first you’ll have to import it. Let me create a list with some content. Note that it is already in sorted order. In this case, I’m using the higher number to indicate a higher priority.

05:08 I’ve done this because I want to use the cheap pop operation to get the most important item from the queue. To use insort(), call it with the list and the new item.

05:20 And like magic, the list remains sorted. I’ll just insert something else.

05:32 And one more.

05:36 Notice what is happening here with the sorting. Because there are three items in this list whose first value is the number 3, the sorting continues to the second item in the tuple, sorting the objects alphabetically. This is good and bad.

05:50 It means you won’t forget any corner cases in your sorting of data, but it also means you’re stuck with how insort() decides to sort objects.

06:00 Enough with the manual maintaining of priority queues! Can’t you just do it for me? Sure enough, in the next lesson, I’ll introduce you to heapq and PriorityQueue.