Hands-On Data Structures and Algorithms with Python - Second Edition

Priority queues and heaps

A priority queue is a data structure which is similar to the queue and stack data structures that stores data along with the priority associated with it. In the priority queue, the item with the highest priority is served first. Priority queues are often implemented using a heap, since it is very efficient for this purpose; however, it can be implemented using other data structures. It is a modified queue that returns the items in the order of highest priority, whereas the queue returns the items in the order that the items were added. The priority queue is used in many applications, such as CPU scheduling.

Let's consider an example to demonstrate the importance of priority queues over regular queues. Assume that, ...