A heap is a tree-shaped structure that keeps the smallest or largest value easy to access. In Python, heapq implements a min-heap using a list.
Heaps are useful when the algorithm repeatedly needs the current best candidate.
Core Idea
A heap does not keep every element fully sorted. It only maintains enough order to remove the smallest item efficiently.
In Python’s heapq, heappush adds an item and heappop removes the smallest item. Each operation is O(log n).
Python Example
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
smallest = heapq.heappop(heap)smallest is 2.
Common Confusions
A heap is not a sorted list. Looking at the internal list may not show sorted order.
Python’s heapq is a min-heap. For max-heap behavior, a common technique is to store negative numbers or reversed priorities.
When To Use It
Use a heap for top-k problems, scheduling, merging sorted streams, and graph algorithms that repeatedly choose the lowest-cost candidate.