Locked learning resources

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

Unlock This Lesson

Locked learning resources

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

Unlock This Lesson

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.