Priority Queue: heapq
Learn priority queue in python
Priority Queue: heapq
A priority queue is a data structure where each element has a priority, and the element with the highest (or lowest) priority is always served first — regardless of insertion order.
Python's heapq module implements a min-heap: the smallest element is always at the top and can be retrieved in O(1). Insertion and removal are O(log n).
How a Heap Works
A heap is a binary tree stored as a list where every parent is smaller than its children. The smallest element is always at index 0:
Stored as: [1, 3, 5, 4, 8, 7, 9]
You never need to manage the tree structure manually — heapq handles it entirely through the list.
Basic Operations
| Operation | Code | Complexity |
|---|---|---|
| Push | heappush(h, x) | O(log n) |
| Pop minimum | heappop(h) | O(log n) |
| Peek minimum | h[0] | O(1) |
| Build heap from list | heapify(lst) | O(n) |
| Size |