Implementing a Priority Queue
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.
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.
.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.
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.
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: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.
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.
Looking at the result, and now it is by alphabetic order, with the
'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.
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.
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.
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.
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.
Become a Member to join the conversation.