Priority queue in Python

By: On:

In this Python tutorial, we will discuss the priority queue in python. Also, We will see these below topics as:

  • What is the priority queue in python?
  • Python priority queue implementation
  • Max priority queue in python
  • Priority queue using a python library
  • Priority queue implementation using heapq in python
  • Python heapq example
  • Python Priority Queue vs heapq

What is the priority queue in python?

What is the priority queue in python? A priority queue in python is an advanced type of queue data structure. Instead of dequeuing the oldest element, a priority queue sorts and dequeues elements based on their priorities. A priority queue is commonly used for dealing with scheduling problems. It gives precedence to tasks with higher urgency.


Python Priority queue implementation

To implement a priority queue in Python, we have to declare an empty Python list into which elements are inserted using the append() method of list class. The list is then sorted in ascending order. The While loop is used to retrieve the elements using the pop() method.

Example:

student = []
student.append((5, 'Nick'))
student.append((1, 'Rohan'))
student.append((3, 'Jack'))
student.sort(reverse=True)
while student:
    t = student.pop()
    print(t)

After writing the above code (python priority queue implementation), Ones you will print ” t “ then the output will appear as “ (1, ‘Rohan’) (3, ‘Jack’) (5, ‘Nick) ”. Here, the element sorts and dequeue elements based on their priority queue.

You can refer to the below screenshot for python priority queue implementation.


Python Priority queue
Python Priority queue implementation

Max priority queue in Python

Now, let us understand max priority queue in Python.

In the Python max priority queue, the list will be arranged in descending order of their priority. The While loop is used to retrieve the elements using the pop(0) method.

Example:

student = []
student.append((5, 'Nick'))
student.append((1, 'Rohan'))
student.append((3, 'Jack'))
student.sort(reverse=True)
while student:
    t = student.pop(0)
    print(t)

After writing the above code (max priority queue in python), Ones you will print “t” then the output will appear as “ (5, ‘Nick) (3, ‘Jack’) (1, ‘Rohan’). Here, the list is sorted in descending order and dequeue elements based on their priority queue.

You can refer to the below screenshot for max priority queue in python.

Max priority queue in python
Max priority queue in python

Priority queue using a Python library

Let us see how we can implement Priority queue using a Python library.

Python provides a built-in implementation of a priority queue. The queue module is imported and the elements are inserted using the put() method. The while loop is used to dequeue the elements using the get() method. The time complexity of the queue.PriorityQueue class is O(log n).

Example:

from queue import priorityQueue
q = PriorityQueue()
q.put((10,'Red balls'))
q.put((8,'Pink balls'))
q.put((5,'White balls'))
q.put((4,'Green balls'))
while not q.empty():
    item = q.get()
    print(item)

After writing the above code (priority queue using a python library), Ones you will print ” item “ then the output will appear as “ (4, ‘Green balls’) (5, ‘White balls’) (8, ‘Pink balls’) (10, ‘Red balls’) ”. Here, the list is sorted in ascending order and dequeue elements based on their priority queue.

You can refer to the below screenshot for priority queue using a python library.

Priority queue using a python library
Priority queue using a python library

Priority queue implementation using heapq in python

We can also use heapq module in python to implement a priority queue. We will import heapq from the library and then created an empty list. But heapq only provides the min-heap implementation.

Example:

import heapq
s_roll = []
heapq.heappush(s_roll,(4, "Tom"))
heapq.heappush(s_roll,(1, "Aruhi"))
heapq.heappush(s_roll,(3, "Dyson"))
heapq.heappush(s_roll,(2, "Bob"))
While s_roll:
    deque_r = heapq.heappop(s_roll)
    print(deque_r)

After writing the above code (priority queue implementation using heapq in python), Ones you will print ” deque_r “ then the output will appear as “ (1, ‘Aruhi’) (2, ‘Bob’) (3, ‘Dyson’) (4, ‘Tom’) ”. Here, by using heappush() method of the heapq module, we inserted the elements into the list. While loop is then used to pop elements out.

You can refer to the below screenshot priority queue implementation using heapq in python.

Priority queue implementation using heapq in python
Priority queue implementation using heapq in python

Python heapq example

We will use heapq class to implement heaps in python. In heapq by default, min-heap is implemented by this class.

Example:

from heapq import heapify, heappush, heappop
heap = []
heapify(heap)
heappush(heap, 5)
heappush(heap, 40)
heappush(heap, 30)
heappush(heap, 50)
print("Minimum value of heap is : "+str(heap[0]))
print("The heap element : ")
for i in heap:
    print(i, end = ' ')
print("\n")
element = heappop(heap)
print("The heap element : ")
for i in heap:
    print(i, end= ' ')

After writing the above code (python heapq example), Ones you will print then the output will appear as “ Minimum value of heap is : 5 ”. Here, by using heappush() method of the heapq module, we inserted the elements into the heap and it will print the value of the minimum element.

You can refer to the below screenshot python heapq example

Python heapq example
Python heapq example

Python Priority Queue vs heapq

Priority Queueheapq
Queue.PriorityQueue is a thread-safe classheapq module makes no thread-safety
In queue.PriorityQueue, you can use the usual queue method put() to add items.In heapq, you can use the method heappush() to add new items.
In queue.PriorityQueue, you can use the usual queue method get() to remove.In heapq, you can use the method heappop() to remove.

You may like the following Python tutorials:

In this Python tutorial, we have learned about the priority queue in python. Also, We covered these below topics:

  • What is the priority queue in python?
  • Python priority queue implementation
  • Max priority queue in python
  • Priority queue using a python library
  • Priority queue implementation using heapq in python
  • Python heapq example
  • Python Priority Queue vs heapq

Leave a Comment