Priority Queue

A priority queue acts like a queue in that you dequeue an item by removing it from the front. However, in a priority queue the logical order of items inside a queue is determined by their priority. The highest priority items are at the front of the queue and the lowest priority items are at the back. Thus when you enqueue an item on a priority queue, the new item may move all the way to the front.

Ways to implement a priority queue using sorting functions and lists. However, inserting into a list is O(n) and sorting a list is O(nlogn). We can do better. The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us both enqueue and dequeue items in O(logn).

The binary heap has two common variations: the min heap, in which the smallest key is always at the front, and the max heap, in which the largest key value is always at the front.

Examples

• Donar/recipient list for organ transplant.

• CPU Scheduling

Priority Queue Abstract Data Type

The priority queue abstract data type is defined by the following structure and operations. A priority queue is structured, as described above, as an ordered collection of items which are added at one end, called the “rear”, and removed from the other end, called the “front”. Queues maintain a FIFO ordering property.

Priority Queue Operations

• PriorityQueue() creates a new priority queue that is empty. It needs no parameters and returns an empty queue.

• enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.

• dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.

• is_empty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.

• size() returns the number of items in the queue. It needs no parameters and returns an integer.

q = Queue() creates a queue that starts out empty, table below shows the results of a sequence of queue operations.

Queue Operation	Queue Contents	Return Value
pq.is_empty()	[]	True
pq.enqueue(4)	[4]
pq.enqueue('dog')	['dog',4]
pq.enqueue('True')	[True,'dog',4]
pq.size()	[True,'dog',4]	3
pq.is_empty()	[True,'dog',4]	False
pq.enqueue(8.4)	[8.4,True,'dog',4]
pq.dequeue()	[8.4,True],'dog']	4
pq.dequeue()	[8.4,True]	'dog'
pq.size()	[8.4,True]	2

Implementing a Queue in Python

An abstract data type (ADT) when given a physical implementation then we refer to the implementation as a data structure.

In any object-oriented programming language, the implementation of choice for an abstract data type such as a Queue is the creation of a new class. The queue operations are implemented as methods. Further, to implement a queue, which is a collection of elements, it makes sense to utilize the primitive collections provided.

Python provides List an ordered collection mechanism and a set of methods, rear is at position 0 in the list. This allows us to use the insert function on lists to add new elements to the rear of the queue. The pop operation can be used to remove the front element (the last element of the list). Recall that this also means that enqueue will be O(n) and dequeue will be O(1).

pq = PriorityQueue() creates a queue that starts out empty, table below shows the results of a sequence of queue operations.

Queue Operation	Queue Contents	Return Value
pq.is_empty()	[]	True
pq.enqueue(4)	[4]
pq.enqueue('dog')	['dog',4]
pq.enqueue('True')	[True,'dog',4]
pq.size()	[True,'dog',4]	3
pq.is_empty()	[True,'dog',4]	False
pq.enqueue(8.4)	[8.4,True,'dog',4]
pq.dequeue()	[8.4,True],'dog']	4
pq.dequeue()	[8.4,True]	'dog'
pq.size()	[8.4,True]	2

Implementing a Queue in Python

An abstract data type (ADT) when given a physical implementation then we refer to the implementation as a data structure.

In any object-oriented programming language, the implementation of choice for an abstract data type such as a Queue is the creation of a new class. The queue operations are implemented as methods. Further, to implement a queue, which is a collection of elements, it makes sense to utilize the primitive collections provided.

Python provides List an ordered collection mechanism and a set of methods, rear is at position 0 in the list. This allows us to use the insert function on lists to add new elements to the rear of the queue. The pop operation can be used to remove the front element (the last element of the list). Recall that this also means that enqueue will be O(n) and dequeue will be O(1).

class PriorityQueue:
    
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

# Create a new queue
pq = PriorityQueue()

# Check if the queue is empty
print(pq.is_empty())

# Enqueue 4 at rear of queue
pq.enqueue(4)

# Enqueue "dog" at rear of queue
pq.enqueue('dog')

# Enqueue "True" at rear of queue
pq.enqueue(True)

# Give the size of the queue
print(pq.size())

# Check if the queue is empty
print(pq.is_empty())

# Enqueue 8.4 at rear of queue
pq.enqueue(8.4)

# Dequeue the rear element from the queue and return it
print(pq.dequeue())

# Dequeue the rear element from the queue and return it
print(pq.dequeue())

# Give the size of the queue
print(pq.size())

True
3
False
4
dog
2

Practical usage in python

heapq module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.

Heaps are arrays for which a[k] <= a[2k+1] and a[k] <= a[2k+2] for all k, counting elements from 0. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that a[0] is always its smallest element.

By default heapq in standard liberary implements Min-Heap only. And you can find more information about the interface and api from docs.