Back to Topics
Heap
A heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is ≤ its children; in a max-heap, every parent is ≥ its children. This guarantees O(1) access to the minimum (or maximum) element and O(log n) insertion/deletion. Heaps power priority queues and the top-K family of problems.
Key Ideas
- Min-heap: root is always the smallest element — peek min in O(1)
- Max-heap: root is always the largest element
- Python's heapq module is a min-heap; negate values for max-heap behaviour
- Building a heap from n elements takes O(n) — faster than n × O(log n) insertions
- Top-K largest elements: maintain a min-heap of size K; O(n log K)
- Median of a data stream: two heaps — max-heap for lower half, min-heap for upper half
Complexity
| Operation | Time | Space |
|---|---|---|
| Peek min/max | O(1) | O(1) |
| Insert | O(log n) | O(1) |
| Extract min/max | O(log n) | O(1) |
| Build heap | O(n) | O(n) |
| Heap sort | O(n log n) | O(1) |
Common Patterns
Top-K ElementsPush all elements; pop K times. Or maintain a size-K heap for O(n log K).
K-way MergePush the head of each sorted list into a min-heap; repeatedly extract min and advance that list.
Two-heap MedianLower half in max-heap, upper half in min-heap; balance sizes to read median in O(1).
Dijkstra's (greedy)Priority queue of (cost, node); always process the cheapest unvisited node first.
Code Example
K-th largest element in an arraypython
import heapq
def find_kth_largest(nums: list[int], k: int) -> int:
# Min-heap of size k — root is k-th largest
min_heap: list[int] = []
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap) # evict smallest
return min_heap[0] # root = k-th largest💡
Whenever a problem mentions 'top K', 'K closest', or 'K most frequent', reach for a heap.