Priority Queue

A priority queue returns items by priority, not by insertion time.

Example:

• urgent tasks first
• shortest job first
• routing algorithms

In Python, we use heapq.

Basic heap (min-heap)

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 3

Store (priority, value)

import heapq

pq = []
heapq.heappush(pq, (1, "urgent"))
heapq.heappush(pq, (5, "low"))
heapq.heappush(pq, (2, "medium"))

while pq:
    priority, task = heapq.heappop(pq)
    print(priority, task)

Max-heap trick

heapq is min-heap. To simulate max-heap, store negative priorities.

import heapq

pq = []
heapq.heappush(pq, (-10, "high"))
heapq.heappush(pq, (-1, "low"))

print(heapq.heappop(pq))  # (-10, 'high')

Graph: heap property (intuition)

flowchart TD
  A[Min heap] --> B[Smallest item at top]
  B --> C[Pop gives smallest first]

Remember

• Use heapq for priority queues
• Great for scheduling and shortest-first problems
• Store (priority, item) for clean logic