Heaps & Priority Queues
Heaps give you the min/max in O(1) and add/remove in O(log n). Learn heapify and priority queues.
Lessons
1. Intro
Efficient extrema access
2. Vocabulary - Heap
Complete binary tree
3. Heap Visualization
See the structure
4. Array Representation
No pointers needed
5. Heap Operations Overview
What heaps support
6. Insert Operation
Bubble up
7. Extract Operation
Bubble down
8. Bubble Down Details
Choosing the right child
9. Vocabulary - Priority Queue
Abstract interface
10. Using Built-in Heaps
Language specifics
11. Quiz: Heap Basics
Time complexity
12. Problem - Last Stone Weight
Simple heap problem
13. Last Stone - Algorithm
Max-heap simulation
14. Last Stone - Implementation
Complete solution
15. Lessons from Last Stone
Repeated max access
16. The K-th Element Problem
Finding rank k
17. K-th Largest with Min-Heap
The counterintuitive choice
18. Problem - Kth Largest Element
Classic heap problem
19. Kth Largest - Algorithm
Bounded min-heap
20. Kth Largest - Implementation
Complete solution
21. Lessons from Kth Largest
Heap size matters
22. Quiz: K-th Element
Heap type choice
23. Problem - Top K Frequent Elements
Frequency + heap
24. Top K Frequent - Algorithm
Two-phase approach
25. Top K Frequent - Implementation
Complete solution
26. Lessons from Top K Frequent
Combining structures
27. The Merge Problem
K-way merge
28. K-Way Merge with Heap
The algorithm
29. Problem - Merge K Sorted Lists
Classic interview problem
30. Merge K Lists - Implementation
Complete solution
31. Lessons from Merge K Lists
Frontier tracking
32. Quiz: K-Way Merge
Complexity analysis
33. The Median Problem
Running median challenge
34. Two Heaps Technique
Split at the median
35. Two Heaps Visualization
See the split
36. Problem - Find Median from Data Stream
Two heaps in action
37. Median Stream - Invariants
What to maintain
38. Median Stream - Implementation
Complete solution
39. Lessons from Median Stream
Two heaps pattern
40. Quiz: Two Heaps
Insertion order
41. When to Use Heaps
Pattern signals
42. Heap vs Sorting
When each wins
43. Section Recap
What we learned
Practice Problems
Perfect introduction to heap operations (insert, getMin, removeMin) with a greedy approach. Construct valid operation sequences.
Excellent k-th order statistics problem. Forces you to use Fenwick Trees or creative frequency array approaches.
Classic greedy with priority queue. Maximize pleasure by sorting by one dimension while maintaining heap for the other.
Combines binary search with greedy heap thinking. Maximize median values by focusing operations on elements from median upward.
Perfect interval scheduling simulation using priority queues. Teaches sweep line algorithm with min-heap for active intervals.
Prim/Dijkstra-style graph traversal using priority queues. Find lexicographically smallest paths.
Interval intersection problem requiring greedy segment selection. Use sorting and binary search with multisets.
Greedy digit construction problem. Maximize number's magnitude while respecting resource constraints.
Tree DP with greedy selection using depth and subtree sizes. Select k nodes that maximize total happiness.
Sorting-based greedy optimization. Great introduction to problems where sorting reveals the greedy strategy.
Bitmask DP combined with sorting and greedy heap optimization. Sort by one dimension for efficient DP on subsets.
Cache replacement with variable costs - weighted LRU algorithm. Requires minimum cost flow or clever greedy heap strategies.
Fundamental problem teaching min-heap to maintain k largest elements in O(n log k) time. Essential Top-K pattern.
Classic two-heap problem (max-heap + min-heap). Teaches advanced heap coordination and balancing for streaming data.
Fundamental FAANG interview problem demonstrating heap-based merging. Widely applicable in system design scenarios.
Combines hash maps with heaps for frequency-based problems. The powerful 'heap + hashmap' pattern.
Advanced scheduling combining heaps with greedy algorithms. Simulate CPU task scheduling with cooldown constraints.
Greedy frequency-based rearrangement using max-heap. Solve character spacing problems to avoid adjacency constraints.
Complex multi-list merging with min-heap and sliding window. Maintain range invariants while processing sorted sequences.
Advanced greedy + heap for capital maximization. Combine sorting with heap-based selection for optimal profit.