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:

• bisect – Array bisection algorithm | Python Documentation
• Sorting Algorithms in Python | Real Python Article
• Binary heap | Wikipedia Article
• heapq – Heap queue algorithm | Python Documentation
• queue – A synchronized queue class: PriorityQueue | Python Documentation

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.