Introduction to Heaps
A Heap is a specialized tree-based data structure that satisfies the Heap Property:
- Min-Heap: The value of each node is greater than or equal to its parent.
- Max-Heap: The value of each node is less than or equal to its parent.
1. Real-World Intuition: The Emergency Room
Imagine a hospital emergency room: patients are treated based on Severity (Priority), not just arrival time. A Priority Queue ensures the "most important" item is always at the front.
2. Curriculum in this Module
- Theory & Intuition (Current Page)
- Problem: Kth Largest Element - Mastering Min-Heaps of size K.
- Problem: Merge K Sorted Lists - Using heads to optimize merging.
- Curated Practice Problems - 10 essential challenges.
3. Java Implementation (PriorityQueue)
// Min-Heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Max-Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Custom Comparator (Object)
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
Final Takeaway
Heaps provide $O(1)$ access to the smallest/largest item and $O(\log n)$ for insertions and deletions. They are the ultimate tool for Streaming Data.