Priority Queue
DSA · Stacks and Queues
Theory
A priority queue always removes the item with the highest priority (or lowest value) first, regardless of insertion order. It is usually implemented with a binary heap, giving O(log n) insert and remove and O(1) peek. Python's heapq module provides a min-heap; negate values for a max-heap.
Why we use it
It always gives you the most urgent item quickly, without re-sorting the whole collection after every change.
When to use it
Use it for task schedulers, Dijkstra's shortest path, merging sorted lists, finding the top-k items, and event simulation.
How it works
- Insert items with priorities
- Store in a min-heap
- Remove? Yes: Pop the smallest priority (root). No: Peek at the root.
- Re-heapify in O(log n)
- Always serves the most urgent item
Syntax
import heapq
heapq.heappush(pq, (priority, item)) O(log n)
heapq.heappop(pq) O(log n)
pq[0] O(1) peekExample
# A simple priority queue using a sorted insert (works everywhere)
class PriorityQueue:
def __init__(self):
self.items = []
def push(self, priority, task):
i = 0
while i < len(self.items) and self.items[i][0] <= priority:
i += 1
self.items.insert(i, (priority, task))
def pop(self):
return self.items.pop(0)
pq = PriorityQueue()
pq.push(3, "Reply to emails")
pq.push(1, "Fix production bug")
pq.push(2, "Code review")
while pq.items:
print(pq.pop())
# In real Python code use heapq for O(log n) push/popKey points
- Highest priority leaves first
- Heap-based: O(log n) push and pop
- heapq is a min-heap in Python
- Used in Dijkstra and schedulers