Overview
A heap is a complete binary tree stored in an array where every parent is no larger than its children (a min-heap) or no smaller (a max-heap). It does not keep everything sorted — only the root is guaranteed to be the extreme — and that relaxed promise is what lets push and pop run in O(log n).
Whenever a problem repeatedly asks for "the smallest so far", "the k largest" or "the next event to happen", reach for a heap. Python's heapq is a min-heap (negate values for a max-heap); C++ std::priority_queue is a max-heap by default (pass greater<> for a min-heap).
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Peek min/max | O(1) |
| Push / pop | O(log n) |
| Build from n items | O(n) |
| Top-k of n items | O(n log k) |
Patterns to recognise
Top-k
Use it for: k-th largest, k closest points, top-k frequent.
Maintain a heap of size k with the "worst kept" item at the root.
K-way merge
Use it for: Merge k sorted lists, smallest range covering k lists.
Push the head of each list; pop the smallest and push its successor.
Greedy scheduling
Use it for: Task scheduler, IPO, meeting rooms.
Always process the most urgent or most profitable available item next.
Code template
import heapq
def find_kth_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest
return heap[0]
int findKthLargest(const vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> heap; // min-heap
for (int x : nums) {
heap.push(x);
if ((int)heap.size() > k) heap.pop(); // drop the smallest
}
return heap.top();
}
Common mistakes
- Mixing up default directions: heapq is a min-heap, priority_queue is a max-heap.
- Pushing tuples whose second element is not comparable — add a counter as a tie-breaker.
- Using a heap when you need to search or remove arbitrary elements; use a balanced BST (std::set) instead.
Quick check
Three questions on Heaps. Get all three right to earn +15 XP.
-
In a min-heap, where is the smallest element?
Every parent is no larger than its children, so the minimum rises to the root.
-
Pushing to or popping from a heap of n elements costs:
The element sifts up or down along one root-to-leaf path.
-
To find the k largest elements of a stream, you keep:
The heap root is the smallest of the current top k; anything larger replaces it. Total O(n log k).
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Kth Largest Element in a StreamLeetCode Easy +20
- Last Stone WeightLeetCode Easy +20
- K Closest Points to OriginLeetCode Medium +40
- Kth Largest Element in an ArrayLeetCode Medium +40
- Task SchedulerLeetCode Medium +40
- Find Median from Data StreamLeetCode Hard +70
- Merge k Sorted ListsLeetCode Hard +70
- IPOLeetCode Hard +70
Stuck on Heaps?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor