- Prepare
- All Platforms
- Programming
- Aptitude
- Syllabus
- Interview Preparation
- Interview Exp.
- Off Campus
- Prime Video
- Prime Mock

- Prime Video
- OffCampus
- Internship
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

No New notification

- Login
- Get Prime

# How to Implement Priority Queues in Python

## Introduction of Priority Queues

A Priority Queue is a data structure that manages a set of elements, each associated with a priority. The primary operations on a priority queue are inserting elements with their priority and extracting the element with the highest (or lowest) priority. Unlike traditional queues or stacks, a priority queue does not follow the first-in-first-out (FIFO) or last-in-first-out (LIFO) principles; rather, it prioritizes elements based on their assigned priorities.

## What are heaps in Python?

In some situations we may need to find the minimum/maximum element among a collection of

elements. We can do this with the help of Priority Queue ADT. A priority queue ADT is a data

structure that supports the operations Insert and DeleteMin (which returns and removes the

minimum element) or DeleteMax (which returns and removes the maximum element).

## Priority Queue ADT

The following operations make priority queues an ADT.

Main Priority Queues Operations

- A priority queue is a container of elements, each having an associated key.
- Insert (key, data): Inserts data with key to the priority queue. Elements are ordered based on key.
- DeleteMin/DeleteMax: Remove and return the element with the smallest/largest key.
- GetMinimum/GetMaximum: Return the element with the smallest/largest key without deleting it.

**Auxiliary Priority Queues Operations**

- kth- Smallest/kth – Largest: Returns the kth-Smallest/kth –Largest key in priority queue.
- Size: Returns number of elements in priority queue.
- Heap Sort: Sorts the elements in the priority queue based on priority (key).

## Priority Queue Applications:

**Priority queues have many applications – a few of them are listed below:**

- Data compression: Huffman Coding algorithm
- Shortest path algorithms: Dijkstra’s algorithm
- Minimum spanning tree algorithms: Prim’s algorithm
- Event-driven simulation: customers in a line
- Selection problem: Finding k th- smallest element

## Python priority queue methods:

A priority queue is a data structure that maintains a set of elements, each associated with a priority, and allows efficient access to and removal of the element with the highest (or lowest) priority. Here are some examples of use cases where priority queues are particularly useful:

**Dijkstra’s Shortest Path Algorithm:**In graph algorithms like Dijkstra’s, a priority queue is used to efficiently select and process nodes with the minimum distance during the traversal.Similar*A Search Algorithm:***to*Dijkstra’s algorithm, the A* search algorithm uses a priority queue to explore paths in order of increasing cost, combining the cost to reach a node and a heuristic estimate of the cost from that node to the goal.**Huffman Coding:**Huffman coding, used in data compression, involves assigning variable-length codes to input characters based on their frequencies. Priority queues help in building the Huffman tree by repeatedly merging the nodes with the lowest frequencies.**Job Scheduling:**In task scheduling scenarios, jobs often have different priorities or deadlines. A priority queue can be used to efficiently schedule and execute jobs based on their priority or deadline.**Operating System Process Scheduling:**Operating systems use priority queues to manage the execution of processes. Processes with higher priority are given preference in execution, ensuring that critical tasks are handled promptly.**Load Balancing:**Priority queues can be employed in load balancing systems to manage tasks or requests based on their priority or urgency, ensuring that important tasks are handled first.**Distributed Systems:**In distributed systems, messages or tasks may have different priorities. Priority queues help in managing the order of processing tasks in a distributed environment.**Event-driven Simulation:**Simulations often involve events that occur at different times and have different priorities. Priority queues can be used to maintain and process events in the order of their occurrence.**Data Compression:**In algorithms like Huffman coding, where symbols need to be encoded based on their frequencies, priority queues are used to efficiently process and merge symbols.**Networking Protocols:**Some networking protocols involve processing packets with different priorities. Priority queues can be employed to handle packets based on their priority levels, ensuring timely processing of critical information.

## Priority Queue Implementations:

**Using a List:**A simple implementation using a list where each element is a tuple of the form (priority, value).

class PriorityQueueList:

def __init__(self):

self.elements = []

def enqueue(self, priority, value):

self.elements.append((priority, value))

self.elements.sort(reverse=True) # Sorting in descending order based on priority

def dequeue(self):

if not self.is_empty():

return self.elements.pop()

def is_empty(self):

return len(self.elements) == 0

**Using heapq Module (Binary Heap):**Python provides a heapq module that allows you to implement a binary heap-based priority queue.

import heapq

class PriorityQueueBinaryHeap:

def __init__(self):

self.elements = []

def enqueue(self, priority, value):

heapq.heappush(self.elements, (priority, value))

def dequeue(self):

if not self.is_empty():

return heapq.heappop(self.elements)

def is_empty(self):

return len(self.elements) == 0

**Using queue.PriorityQueue:**The queue module in Python includes a PriorityQueue class, which is a binary heap-based priority queue.

from queue import PriorityQueue

class PriorityQueueModule:

def __init__(self):

self.elements = PriorityQueue()

def enqueue(self, priority, value):

self.elements.put((priority, value))

def dequeue(self):

if not self.is_empty():

return self.elements.get()

def is_empty(self):

return self.elements.empty()

### Prime Course Trailer

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

**Get over 200+ course One Subscription**

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Login/Signup to comment