DSA — Priority Queues

What is a Priority Queue?

A queue where each element has a priority, and higher priority elements are dequeued first.

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
    
    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))
    
    def pop(self):
        return heapq.heappop(self.heap)[1]
    
    def is_empty(self):
        return len(self.heap) == 0

Using heapq

import heapq

# Create priority queue
pq = []

# Push items (priority, value)
heapq.heappush(pq, (1, 'low'))
heapq.heappush(pq, (3, 'high'))
heapq.heappush(pq, (2, 'medium'))

# Pop items
while pq:
    priority, value = heapq.heappop(pq)
    print(f"Priority {priority}: {value}")

Operations

Operation	Time Complexity
Push	O(log n)
Pop	O(log n)
Peek	O(1)

Use Cases

• Task scheduling
• Dijkstra's algorithm
• Huffman coding
• Event-driven simulation

Mini Practice

1. Implement a priority queue
2. Use for task scheduling
3. Implement job scheduler
4. Use in Dijkstra's algorithm

Up Next

Continue with Graphs — graph data structure.