What are different ways to implement a priority queue in Python?

Before we get into implementing a priority queue in Python, let us first understand what a priority queue is. Priority queues are data structures where each element in the queue has a certain priority. A priority queue sorts and dequeues elements based on their priority.

Rules to implement a priority queue

1. High priority element is dequeued before low priority element.
2. In the case of elements having the same priority, they are dequeued by their order.

Simple implementation of a priority queue

##implement using low priority elements to high priority elements
pq=[]
pq.append(100)
pq.append(90)
pq.append(80)
pq.append(70)
pq.append(60)
pq.append(50)
pq.append(40)
pq.append(30)
pq.append(20)
pq.append(10)
print(pq)

pq.sort()
print(pq)

pq.pop()
pq.pop()
pq.pop()
pq.pop()
print(pq)

What is a binary heap?

A data structure is in the form of a binary tree. They are a common way of implementing a priority queue. The element at the root of the tree will always have the highest priority.

Trees are non-linear data structures that represent nodesconnected by edges. Each tree consists of a root node as the Parent node, and the left node and right node as Child nodes.

A binary tree can be represented by using a list where every node consists of three fields. The first field for storing value of root node, second for storing list that represents the left subtree, and third for storing list that represents the right subtree.

Syntax: [root node, left subtree as list, right subtree as list]

Note: A binary heap is either maximum or minimum.

1.Min-heap: The value of a parent node is less than or equal to its children nodes.

2.Max-Heap: The value of a parent node is greater than or equal to its children nodes.

What is a heap queue?

Heap queue (heapq): It is an implementation of the priority queue algorithm in which the properties of the min-heap are preserved.

Note: Refer above for the definition of min-heap.

Operations of the heapq module

1.heapify(iterable): Conversion of the iterable into a heap data structure.

2.heappush(heap, element): To insert the element argument into the heap.

3.heappop(heap): To remove the smallest element from the heap.

4.heappushpop(heap, element): To combine the function of both push (the element) and pop (the smallest element) in one line.

5.heapreplace(heap, element): The smallest element is first popped, then the element argument is pushed.

Implementation of heapq

# Refer above text for more understanding of code
# importing "heapq" to implement heap queue 
import heapq 
# initializing list 
list1 = [1, 5, 10, 15, 20]
# to convert list into heap 
heapq.heapify(list1)
print ("Initial heap: ", list1)
# to push elements into heap 
heapq.heappush(list1, 3) 
# print changed heap
print ("Changed heap: ", list1) 
# to pop smallest element 
print ("The smallest element is popped:", heapq.heappop(list1)) 
# print the updated heap
print ("Updated heap: ",list1)
# to push and pop items simultaneously 
print ("The popped item using heappushpop() is : ",list1) 
print (heapq.heappushpop(list1, 3)) 
# to push and pop items simultaneously 
print ("The popped item using heapreplace() is : ",list1) 
print (heapq.heapreplace(list1, 2)) 

Why use heapq to implement a priority queue?

Heap is generally favoured for implementing priority queues as they provide better performance than arrays or linked lists. They are used to execute the program because of the maximum and minimum elements at the root of the tree.