LeetCode Solutions← Back to Patterns
Data StructuresMedium
Heap
Priority queue for always accessing the min or max element in O(log n).
How it works
A Heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is smaller than its children (the minimum is always at the root). Operations: insert (push) is O(log n), remove min/max (pop) is O(log n), peek is O(1). The Heap is the foundation of the Priority Queue ADT. In algorithm problems, use a heap when you need repeated access to the smallest or largest element as the set changes. For "top K" problems, maintain a heap of size K — this is O(n log K) instead of O(n log n) for a full sort. Two heaps (one min, one max) can maintain a running median in O(log n) per insert.
Interactive Playground
Min heap: parent ≤ children. Root is always the minimum.
Speed
When to use
- K largest or K smallest elements
- Merge K sorted lists
- Continuously finding the median
✅Tips
1Python's `heapq` is a min-heap. For max-heap, push negative values: `heapq.heappush(h, -val)`.
2For "top K largest", maintain a min-heap of size K — pop when size exceeds K. The root is always the Kth largest.
3Push tuples `(priority, value)` to heap for custom ordering — Python compares tuples lexicographically.
4Running median: use a max-heap for the lower half and a min-heap for the upper half; keep sizes balanced.
❌Common Mistakes
!Using a max-heap naively in Python — heapq only supports min-heap, must negate values.
!For "K largest", using a max-heap of all n elements is O(n log n) — a min-heap of size K is better.
!Not handling ties correctly in custom comparators — add a unique tiebreaker in the tuple.
!Confusing `heapify` (O(n) in-place) with repeatedly calling `heappush` (O(n log n)).
💡 Key Insight:Python uses a min-heap — negate values to simulate a max-heap.