Know this before you start: “What a min-heap / max-heap keeps on top”
What a heap keeps on top
A heap always knows its smallest item (min-heap) or largest (max-heap), right at the top, without keeping everything sorted.
The idea
A heap is a tree packed into an array where every parent is ≤ its children (a min-heap). That one rule guarantees the smallest item is at the top, index 0, while the rest stays only loosely ordered.
Python's heapq module is a min-heap on a plain list. For a max-heap, push the negatives and flip the sign when you read them back.
Use a heap when you repeatedly need the smallest (or largest) item while items keep arriving: sorting again after every insert would be far slower.
See it step by step
Push 5, 1, 8, 3 into a min-heap
- push 5 → top 5; push 1 → top 1
- push 8 → top still 1; push 3 → top still 1
- pop → 1, then the top becomes 3: the next smallest, found automatically.
In code (Python)
import heapq
heap = []
for x in [5, 1, 8, 3]:
heapq.heappush(heap, x)
print(heap[0]) # 1: the smallest is always at index 0
print(heapq.heappop(heap)) # 1
print(heap[0]) # 3
# A max-heap: store negatives
max_heap = []
for x in [5, 1, 8, 3]:
heapq.heappush(max_heap, -x)
print(-max_heap[0]) # 8Peek at the top: O(1). Building a heap from n items: O(n) with heapify.
When you'll use it
- Repeatedly taking the smallest / largest: scheduling, merging sorted lists, Dijkstra, the k-th largest.
Common mistakes
- Assuming the heap list is sorted (only index 0 is guaranteed).
- Forgetting heapq is a min-heap.
