Week 32 of 43
Advanced DSA
WEEK 32 LEARNING MODULE
Heaps & Priority Queues
Covers binary heap invariants (Min-Heap, Max-Heap), array-based tree indexing, $O(n)$ bottom-up heapify, Python heapq, Top-K elements, and running medians.
5 Practice Problems3 Core ConceptsVerified Curriculum: high Confidence
What You'll Learn
- ✓Master Heap properties: Complete Binary Trees satisfying Min-Heap or Max-Heap invariants.
- ✓Understand array-based tree indexing: `left = 2*i + 1`, `right = 2*i + 2`, `parent = (i - 1) // 2`.
- ✓Implement bubble-up ($O(\log n)$), bubble-down ($O(\log n)$), and bottom-up heapify ($O(n)$).
- ✓Use Python `heapq` module for Top-K Frequent Elements, Kth Largest Element, and K-Way Merges.
- ✓Design a two-heap (Min-Heap + Max-Heap) data structure for finding running medians from data streams.
Core Concepts
Heap Invariant
O(1) peekParent key is always <= children (Min-Heap) or >= children (Max-Heap).
Linear Heap Construction (Heapify)
O(n)Building a valid heap bottom-up from an unordered array in O(n) time.
Two-Heap Running Median
O(log n) insert, O(1) findMedianMaintaining a max-heap for lower half and min-heap for upper half to get median in O(1).
Algorithms Covered
Bottom-up Heapify ($O(n)$)Heap Sort ($O(n \log n)$)Top-K Selection ($O(n \log k)$)K-Way Merging ($O(n \log k)$)Two-Heap Running Median
Data Structures Applied
Min-HeapMax-HeapPriority QueueArrays
“Actions express priorities.”
— Mahatma Gandhi