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) ```python 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) ```python 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. ```python import heapq pq = [] heapq.heappush(pq, (-10, "high")) heapq.heappush(pq, (-1, "low")) print(heapq.heappop(pq)) # (-10, 'high') ``` ## Graph: heap property (intuition) ```mermaid 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