DSA Sheet - Day 23 Heaps
🔥 DSA Sheet – Day 23: Heaps (Priority Queue)
This section introduces heap-based problems used for optimizing sorting, top-K queries, and real-time data stream processing — very common in interviews.
📊 Progress Tracker
Progress: 0 / 6 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Merge K Sorted Arrays | Solve | Easy | Amazon, Cisco | |
| Top K Frequent Elements | Solve | Medium | Amazon, Microsoft | |
| Median from Data Stream | Solve | Hard | Google, Amazon | |
| Smallest Range from K Lists | Solve | Hard | Amazon, Adobe | |
| Kth Smallest Element | Solve | Medium | Apple, Salesforce | |
| Heap Sort | Solve | Easy | General |
🧠 Key Approaches
- Merge K Arrays: Min Heap to track smallest elements
- Top K Frequent: Max Heap OR Bucket Sort
- Median Stream: Two heaps (max + min)
- Smallest Range: Min Heap + track max value
- Kth Smallest: Heap OR Binary Search
- Heap Sort: Build heap + extract max/min
⚡ Quick Cheatsheet
Top K Frequent Elements
priority_queue> pq;
// {frequency, element}
Median from Data Stream
// maxHeap → left half
// minHeap → right half
// keep sizes balanced
Kth Smallest Element
priority_queue maxHeap;
// maintain size = k
Heap Sort
// build heap
// repeatedly extract root
🔥 Pro Tip
Heaps are mainly used when:
- You need Top K elements
- You process streaming data
- You want efficient min/max access