Heap
A Heap is a specialized array-based binary tree representing a complete tree. A Min-Heap requires parents to be smaller than children (minimum value at root). Max-Heaps require parents to be larger.
Why It Exists
Priority scheduling requires constant access to min/max items. Heaps keep elements partially sorted in memory, updating in O(log N) time without the cost of sorting a full array.
Intuition for Beginners
“Think of an emergency room triage queue. Patients are sorted dynamically by severity. The most critical patient is treated first (root), while new patients are integrated into the queue based on priority.”
Visual Explanation
Max-Heap Array representation:
Index: 0 1 2 3 4
Array: [90, 30, 40, 10, 20]
Tree:
[90] (0)
/ \
[30] [40] (2)
/ \
[10] [20] (4)Interactive Tracing Sandbox
Interactive step-by-step layout is currently under deployment. Complete trace state maps will be accessible in the next release.
Complexity Analysis
| Operation | Time Complexity | Notes |
|---|---|---|
| Get Min/Max | O(1) | Root node is always at index 0 |
| Insert | O(log N) | Bubbles element up to maintain order |
| Extract Min/Max | O(log N) | Swaps root with last node, bubbles down |
| Heapify | O(N) | In-place tree construction from raw array |
Production & Real World Applications
- •Job Schedulers: Priority runtimes allocating CPU slots to threads.
- •Heap Sort: Sorting arrays in-place with O(N log N) time and O(1) space.
Algorithmic Patterns
Using min-heap and max-heap side-by-side to track dynamic medians in real time.
Pushing sorted list heads into a min-heap to extract sorted values sequentially.
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️Confusing heaps with Binary Search Trees (heaps do not maintain left-to-right sorting).
- ⚠️Calling bubble-up/down on index offsets that do not match child formulas.