Introduction to Priority Queues using Python

November 4, 2023

Introduction to Priority Queues using Python

Introduction to Priority Queues using Python enable us to perform various operations like insertion, deletion, and retrieval of data with optimal time complexity.

In this article, we’ll delve into the concept of Priority Queues, understand their significance, and explore how to implement them using Python.

Priority Queue Python

A Priority Queue is a type of data structure that stores elements with associated priorities. Unlike traditional queues, where elements are retrieved based on the order of insertion (FIFO),

Priority Queues serve elements based on their priority values. Elements with higher priorities are dequeued before those with lower priorities.

Types of Priority Queues

Min Priority Queue In a Min Priority Queue, the element with the lowest priority value is dequeued first. It is suitable for applications where lower values indicate higher priorities.

Max Priority Queue A Max Priority Queue dequeues the element with the highest priority value first. This is used when higher values signify higher priorities.

How to use Priority Queue in Python?

Import the heapq module:

import heapq

Create an empty list to represent your priority queue. You can use this list to store elements along with their priorities:

priority_queue = []

Add elements to the priority queue using the heapq.heappush() function. Each element should be a tuple where the first element is the priority and the second element is the data:

heapq.heappush(priority_queue, (3, 'Task 1'))
heapq.heappush(priority_queue, (1, 'Task 2'))
heapq.heappush(priority_queue, (2, 'Task 3'))

To retrieve the element with the highest priority, you can use the heapq.heappop() function:

highest_priority_task = heapq.heappop(priority_queue)
print(highest_priority_task)  # Output: (1, 'Task 2')

You can continue adding elements and popping elements from the priority queue as needed.
If you want to check if the priority queue is empty, you can use the len() function:

if len(priority_queue) == 0:
    print("Priority queue is empty")
else:
    print("Priority queue is not empty")

Searching Algorithm in Python

Linear Search in Python

Trie In Python

Making a trie Node Class

Recommended for you

How does Python priority queue sort?

In Python, a priority queue is typically implemented using the heapq module, which provides a heap-based priority queue.
Python’s heapq module uses a min-heap to implement a priority queue. A min-heap is a binary tree where the parent node has a smaller (or equal) value than its children.

Insertion: When you insert an element into a heapq priority queue, it is placed in the appropriate position in the binary heap to maintain the heap property. Specifically, it is inserted as a leaf node, and then "bubbled up" to its correct position by repeatedly swapping it with its parent until the heap property is satisfied. This ensures that the smallest element (highest priority) is always at the root of the heap.

Extraction: When you want to retrieve the element with the highest priority (i.e., the smallest element in the case of a min-heap), you simply remove the root of the heap. To maintain the heap property after removal, the last leaf node in the heap is moved to the root position and then "bubbled down" to its correct position by repeatedly swapping it with its smaller child until the heap property is restored.

Implementing Priority Queues in Python

Python offers multiple ways to implement Priority Queues. Let’s explore two common approaches:

Using Lists

One straightforward way to create a Priority Queue in Python is by using lists. You can maintain a list of elements and sort them based on their priorities whenever necessary.

Using Heaps

The heapq module in Python provides a convenient way to implement Priority Queues using binary heaps. Heaps ensure efficient operations, making them an ideal choice.

What are the advantages of priority queues in Python?

Efficient Priority Management: Priority queues are designed to efficiently manage elements with associated priorities. They allow for quick insertion and retrieval of elements with the highest (or lowest) priority.

Optimized for Common Operations: Priority queues are optimized for common operations like inserting elements with priorities and extracting the element with the highest priority.

Space Efficiency: Priority queues use minimal extra memory beyond storing the elements themselves, making them space-efficient.

Predictable Behavior: Priority queues maintain a predictable order for elements based on their priorities. This predictability is essential in scenarios where you need to ensure that the most critical tasks are processed first.

In Python, you can implement a simple Priority Queue using a list and the heapq module. Here’s an example:

Example 1: Priority Queue using Lists

import heapq

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

    def push(self, item, priority):
        heapq.heappush(self.elements, (priority, item))

    def pop(self):
        if self.is_empty():
            raise IndexError("Priority queue is empty")
        return heapq.heappop(self.elements)[1]

    def is_empty(self):
        return len(self.elements) == 0

# Example usage:
pq = PriorityQueue()
pq.push('task1', 3)
pq.push('task2', 1)
pq.push('task3', 2)

while not pq.is_empty():
    print(pq.pop())

In this example, we use a list to store elements, and heapq.heappush and heapq.heappop to maintain the heap property based on the priorities.

Conclusion

In this article, we’ve introduced you to the world of Priority Queues. We’ve explored their significance, types, operations, and implementation in Python. Understanding Priority Queues can significantly enhance your ability to tackle complex problems in the realm of computer science and programming.

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

Unlock this article for Free,
by logging in

Introduction to Priority Queues using Python