Heaps & Priority Queues
Curriculum
Master heap data structures and priority queues through structural invariants, efficient operations, and optimal element access.
What This Category Is Really About
Complete binary tree with ordering constraint. Parent ≥ children (max-heap) or parent ≤ children (min-heap). Enables O(1) min/max access.
Abstract data type: insert elements with priority, extract highest priority. Heaps provide efficient implementation: O(log n) operations.
Bubble up (insert) and bubble down (extract). Restore heap property after modifications. O(log n) time for both operations.
Find K largest/smallest elements efficiently. Maintain heap of size K. Process stream of elements without storing all.
Mental Model & Invariants
Heaps are partially ordered trees optimized for priority access.
"The heap property holds at every node: parent dominates children. This partial ordering enables O(1) peek and O(log n) insert/extract."
Break this, and you lose O(1) access to min/max element.
Heap Property
Max-heap: parent ≥ children. Min-heap: parent ≤ children. Holds at every node in tree.
Complete Tree
All levels filled except possibly last. Last level filled left to right. Enables array representation.
Height Guarantee
Complete tree ensures height = O(log n). All operations proportional to height.
Bubble to Restore
Insert: bubble up from bottom. Extract: replace root with last, bubble down. Both restore heap property in O(log n).
When to Think "Heaps"
sensorsStrong Signals
Need repeated access to min/max element
Top-K largest or smallest elements
Merge K sorted lists/arrays
Streaming data with priority
Scheduling problems
Median maintenance
ruleProblem Signals
Don't need full sort, just extremes
Process elements by priority
Maintain partial ordering efficiently
Dynamic dataset with priority queries
Core Patterns You Must Master
Top-K Elements
Maintain heap of size K. For K largest, use min-heap. For K smallest, use max-heap.
Heap size never exceeds K. Root is Kth element.
Merge K Sorted Lists
Use min-heap with one element from each list. Extract min, add next from same list.
Heap contains at most K elements. Always extract global minimum.
Running Median
Two heaps: max-heap for lower half, min-heap for upper half. Balance sizes.
Max-heap size ≈ min-heap size. Max-heap root ≤ min-heap root.
Task Scheduling
Priority queue ordered by deadline or priority. Process tasks in optimal order.
Next task to process is always at heap root.
Heap Construction
Build heap from array in O(n) using bottom-up heapify. More efficient than n insertions.
Process from last non-leaf upward. Each subtree heapified.
Heap Sort
Build max-heap, repeatedly extract max. In-place sorting algorithm.
Heap shrinks from end. Sorted portion grows from end.
How to Learn This Category
Understand Heap Property
Draw heap as tree and array. Understand parent-child relationships. Practice converting between representations.
Implement Basic Operations
Code insert (bubble up) and extract (bubble down) from scratch. Trace execution step by step.
Master Array Indexing
Parent at i, children at 2i+1 and 2i+2. Practice navigating heap using array indices.
Learn Top-K Pattern
Use min-heap for K largest, max-heap for K smallest. Understand why heap size is K, not n.
Practice Two-Heap Technique
Running median problem. Balance two heaps. Understand when to rebalance.
Study Heap Construction
Build heap in O(n) using bottom-up heapify. Understand why it's faster than n insertions.
Canonical Problem List
auto_awesome_motionFoundation
Kth Largest Element in Array
Use min-heap of size K. Classic top-K pattern.
Last Stone Weight
Max-heap simulation. Extract two largest, insert difference.
K Closest Points to Origin
Max-heap of size K. Maintain K closest points.
Top K Frequent Elements
Count frequencies, use min-heap for top K.
auto_awesome_motionIntermediate
Merge K Sorted Lists
Min-heap with one node from each list. Extract min, add next.
Find Median from Data Stream
Two heaps: max-heap for lower half, min-heap for upper half.
Task Scheduler
Priority queue for task frequencies. Greedy scheduling.
Kth Smallest Element in Sorted Matrix
Min-heap with matrix traversal. K extractions.
Reorganize String
Max-heap by character frequency. Greedy placement.
auto_awesome_motionAdvanced
Sliding Window Median
Two heaps with element removal. Balance after each slide.
IPO
Two heaps: available projects and capital. Maximize profit.
Minimum Cost to Hire K Workers
Heap with ratio sorting. Track wage sum dynamically.
Find K Pairs with Smallest Sums
Min-heap with pair generation. Avoid duplicates.
Common Mistakes
Wrong Heap Type for Top-K
Using max-heap for K largest or min-heap for K smallest. Heap fills with wrong elements.
K largest → min-heap (evict smallest). K smallest → max-heap (evict largest).
Not Maintaining Heap Size
Letting heap grow unbounded. Defeats purpose of top-K pattern.
After inserting, if size > K, extract root. Maintain exactly K elements.
Incorrect Array Indexing
Off-by-one errors in parent/child calculations. Heap property violated.
Parent: (i-1)/2. Left child: 2i+1. Right child: 2i+2. Verify with small examples.
Forgetting to Heapify After Extract
Replacing root but not bubbling down. Heap property broken.
After replacing root with last element, bubble down to restore heap property.
Comparing Wrong Elements in Two-Heap
Not maintaining max-heap root ≤ min-heap root. Median calculation incorrect.
After insertion, check if max-heap root > min-heap root. Swap if needed.
Interview Guidance
What they test
- →Heap type selection (min vs max)
- →Top-K pattern recognition
- →Time complexity analysis
- →Heap property maintenance
Strategy
Identify if problem needs min/max access. For top-K, use opposite heap type. Explain heap property and why operations are O(log n). Mention space complexity.
The Verbal Template
"This is a [top-K / merge / median / scheduling] problem. I need [min/max] access."
"I'll use [min-heap / max-heap] because [reason: maintain K largest / extract minimum / etc]."
"Insert is O(log n) bubble up. Extract is O(log n) bubble down. Peek is O(1)."
"Time: O(n log k) for n elements with heap size k. Space: O(k) for the heap."
When You've Mastered It
Choose min vs max heap instantly
Implement insert and extract correctly
Recognize top-K pattern immediately
Navigate heap using array indices
Maintain heap property after operations
Analyze time complexity accurately
What This Unlocks Next
Advanced Graph Algorithms
Dijkstra's shortest path uses min-heap. Prim's MST uses priority queue. A* search with heuristic priority.
Advanced Sorting
Heap sort, external sorting with K-way merge. Partial sorting for top-K without full sort.
Streaming Algorithms
Maintain statistics on unbounded streams. Running median, top-K frequent, approximate quantiles.
Scheduling & Optimization
Task scheduling, resource allocation, event simulation. Greedy algorithms with priority queues.