Join us and get access to hundreds of tutorials and a community of expert Pythonistas.

Unlock This Lesson

This lesson is for members only. Join us and get access to hundreds of tutorials and a community of expert Pythonistas.

Unlock This Lesson

Hint: You can adjust the default video playback speed in your account settings.
Hint: You can set the default subtitles language in your account settings.
Sorry! Looks like there’s an issue with video playback 🙁 This might be due to a temporary outage or because of a configuration issue with your browser. Please see our video player troubleshooting guide to resolve the issue.

Choosing a Priority Queue

A priority queue is a special instance of a queue where the storage order is based on the priority of the items inside. This is typically used for scheduling algorithms, making some items more important in the schedule than others.

There are several ways to get a priority queue in Python. You can use the built-in list type combined with the sort() function, to sort based on priority. Or, instead of using .sort() you can use bisect.insort() that does insertion sorting. Alternatively, the heapq library provides ways of storing a max-binary-heap in a list, where the priority of the item is the sorting criteria in the heap.

All of the above methods are not thread safe. For a thread safe implementation, queue.PriorityQueue is an implementation of heapq with atomic locking.

Here are resources and additional documentation about bisect, sorting algorithms, heapq, and PriorityQueue:

Download

Sample Code (.zip)

3.3 KB

Download

Course Slides (.pdf)

762.4 KB

The course is the third part of an ongoing series, exploring how to find the right Data Structure for your projects. The first course is Dictionaries and Arrays: Selecting the Ideal Data Structure and the second course is Records and Sets: Selecting the Ideal Data Structure.

Become a Member to join the conversation.