← Back to Data Structures and Algorithms in Python

1. Introduction

A Priority Queue is an abstract data type similar to a regular queue or stack data structure, but where each element has a priority. Elements with higher priorities are served before elements with lower priorities. A common use of priority queues is in algorithms like Dijkstra's shortest path.

2. Implementation Steps

1. Utilize Python's inbuilt heapq module, which turns lists into binary heaps with heappush and heappop methods.

2. Define the enqueue method to add an element and its priority to the queue.

3. Define the dequeue method to remove the item with the highest priority.

4. Implement a method called is_empty to check if the priority queue is empty.

5. Implement a method called size to get the number of elements in the priority queue.

3. Implementation in Python

import heapq
class PriorityQueue:
    def __init__(self):
        # Initialize an empty priority queue
        self.items = []
    def enqueue(self, item, priority):
        # Add an item with its priority to the queue
        heapq.heappush(self.items, (priority, item))
    def dequeue(self):
        # Remove and return the highest priority item from the queue
        if not self.is_empty():
            return heapq.heappop(self.items)[1]
        return None
    def is_empty(self):
        # Check if the priority queue is empty
        return len(self.items) == 0
    def size(self):
        # Return the number of items in the queue
        return len(self.items)
# Test the PriorityQueue class
pq = PriorityQueue()
pq.enqueue("task1", 3)
pq.enqueue("task2", 1)
pq.enqueue("task3", 2)
print("Dequeued item:", pq.dequeue())  # Should print task2

Output:

Dequeued item: task2

Explanation:

1. We start by importing the heapq module, which provides functions to convert a list into a binary heap.

2. The enqueue method uses heappush to insert an item and its priority into the priority queue. The lowest priority number has the highest priority, making this a min-heap.

3. The dequeue method uses heappop to remove and return the item with the highest priority (lowest priority number).

4. The is_empty method checks if the priority queue is empty by determining if the length of items is 0.

5. The size method returns the number of items currently in the priority queue.