Table of contents

Introduction

Heaps

2.1.

Examples of Valid Complete Binary Trees:

2.2.

Examples of Invalid Complete Binary Trees:

2.3.

Heap Property:

Implementation of Max Priority Queue using Python

3.1.

Output:

3.2.

Time Complexity:

Some Important Practice Problems on Priority Queue

Key Takeaways

Last Updated: Dec 18, 2024

Priority Queue using Python

Author Hussain Kagdi

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

A priority queue is one of the elementary data structures used heavily in competitive programming and is one of the favorite topics of interviewers. In this blog, we will code the priority queue using Python.

With one exception, priority queues function in the same manner as normal queues. Each element in the priority queue has a priority associated with it based on which it can be classified into two types :

Min Priority Queue: Minimum element has the highest priority.
Max Priority Queue: Maximum element has the highest priority.

Usually, priority queues are used whenever we need to perform operations based on priority. So, with a priority queue, we can easily extract the highest priority element and complete the required operations.

Internally, priority queues are implemented as heaps.

A min priority queue can be implemented using a min-heap, and a max priority queue can be implemented using a max heap. So let us briefly discuss the concepts of heaps, which will help us implement the priority queue.

Also See, Intersection in Python, Swapcase in Python

Heaps

Heap is an almost complete binary tree with the heap property imposed on it.

A binary tree is an almost complete binary tree if its H - 1 level is filled and the last level is filled from left to right without leaving any intermediary node empty. (‘H’ is the height of the binary tree).

Examples of Valid Complete Binary Trees:

Examples of Invalid Complete Binary Trees:

This is an essential property of the heap, which allows us to represent binary trees efficiently using arrays. The root node is kept at index 0, followed by other nodes in a level order fashion.

For Example:

The above complete binary tree can be stored in an array in the following manner:

If the parent is at index ‘i’ and indexing is 0 based, the left child can be found at index ‘2 * I + 1’, and the right child can be found at index ‘2 * I + 2’.

If the index of the child is ‘i’, then the parent can be found at index ‘(I - 1) / 2’.

Heap Property:

In a min-heap, every parent’s value is less than all the elements in the left subtree and the right subtree and it is followed recursively down the tree.

In a max heap, every parent’s value is greater than all the elements in the left subtree, and the right subtree and it is followed recursively down the tree.

For example:

In the first binary tree, the root node is maximum, and in the second binary tree, the root node is minimum.

Based on the above concepts, let us now see the implementation of the priority queue using python.

Implementation of Max Priority Queue using Python

heap = [0] * 1000
size = -1

# Parent of child node at index ‘i’.
def parent(i) :

return (i - 1) // 2

# LeftChild of the parent at index ‘i’.
def leftChild(i) :

  return ((2 * i) + 1)

# Right child of the parent at index ‘i’.
def rightChild(i) :

  return ((2 * i) + 2)

# Maintaining the heap property.
def upHeapify(i) :

  while (i > 0 and heap[parent(i)] < heap[i]) :

swap(parent(i), i)

i = parent(i)

# Maintaining the heap property.
def downHeapify(i) :

maxIndex = i
l = leftChild(i)

  if (l <= size and heap[l] > heap[maxIndex]) :

maxIndex = l

r = rightChild(i)

  if (r <= size and heap[r] > heap[maxIndex]) :

maxIndex = r

  if (i != maxIndex) :

swap(i, maxIndex)
downHeapify(maxIndex)

# Inserting an element to the priority queue.
def insert(p) :

  global size
size = size + 1
heap[size] = p

upHeapify(size)

# Deleting the maximum element (root element).
def extractMax() :

  global size
result = heap[0]

heap[0] = heap[size]
size = size - 1

downHeapify(0)
  return result

# Returning the maximum element(root element).
def getMax() :

  return heap[0]

# Deleting a particular node.
def delete(i) :

heap[i] = getMax() + 1

upHeapify(i)

extractMax()

# Swapping two nodes.
def swap(i, j) :

temp = heap[i]
heap[i] = heap[j]
heap[j] = temp

def printnodes():

j = 0

while (j <= size) :

print(heap[j], end = " ")

j += 1

print()

insert(45)
insert(20)
insert(14)
insert(12)
insert(31)
insert(7)
insert(11)
insert(13)
insert(7)

print("Priority Queue : ", end = "")

printnodes()

print("Node with maximum priority :" , extractMax())

print("Priority queue after extracting maximum : ", end = "")
printnodes()

delete(3)

print("Priority queue after removing the element : ", end = "")
printnodes()

Output:

Priority Queue : 45 31 14 13 20 7 11 12 7

Node with maximum priority : 45

Priority queue after extracting maximum : 31 20 14 13 7 7 11 12

Priority queue after removing the element : 31 20 14 12 7 7 11

Practice this code with the help of Online Python Compiler

Time Complexity:

The time complexity of upHeapify(), downHeapify(), extractMax(), insert() and remove() is O(log(N)) as in the worst case we have to traverse the no of nodes equal to the height of the tree.
The time complexity of parent(), leftChild(), rightChild(), swap() and getMax() is O(1) since we are doing a constant number of unit operations in each case.

Similarly, we can implement the min priority queue using the min-heap.

Must Read Invalid Syntax in Python.

Some Important Practice Problems on Priority Queue

Why not practice some priority queue problems now that you've learned the concepts? Move ahead to Coding Ninjas Studio to code some famous interview problems on the priority queue. Some of them are listed below:

Key Takeaways

Thank you for reading the blog with patience. After reading the blog, you should have a firm grasp on priority queues and heaps. We learned about the complete binary tree and heap property. We also learned how to implement a priority queue using python and some of its important applications.

Recommended Reading -

Happy Coding!

Live masterclass

Become a YouTube Analyst: Use Python to analyze viewers data

by Coding Ninjas

04 Feb, 2025

02:30 PM

85+ registered

Get hired as an Amazon SDE : Resume building tips

by Coding Ninjas

03 Feb, 2025

02:30 PM

383+ registered

Expert tips: Ace Leadership roles in Fortune 500 companies

by Coding Ninjas

03 Feb, 2025

12:30 PM

72+ registered

Become a YouTube Analyst: Use Python to analyze viewers data

by Coding Ninjas

04 Feb, 2025

02:30 PM

85+ registered

Get hired as an Amazon SDE : Resume building tips

by Coding Ninjas

03 Feb, 2025

02:30 PM

383+ registered

View more events