Two Heaps

What you'll learn

• The Golden Rule

  Use two heaps when you need to: - Find the median from a data stream - Continuously maintain a partition of elements into a lower half and upper half - Quickly access the largest of the small elements and the smallest of the large elemen…

• Why This Structure Works

  Why max-heap for lower half? The root of the max-heap is the largest element in the lower half — which is the left boundary of the median. Combined with the root of the min-heap (smallest of upper half), you have instant access to the mi…

• The Balancing Rule

  The two heaps must stay balanced: - Size difference between them is at most 1 - |len(maxheap) - len(minheap)| ---

• Sliding Window Median

  Problem: Find the median of each window of size k as it slides across the array.

• Challenge: Removing Elements from Heaps

  Standard heaps do not support efficient deletion of arbitrary elements. Solution: lazy deletion.

• Lazy Deletion Strategy

  1. Keep a hash map counting elements that should be deleted 2. When an element leaves the window, mark it for deletion (increment count in map) 3. Only actually remove elements when they appear at the root of a heap 4. Track "effective s…

• Maximize Capital

  Problem: You have initial capital W. There are n projects, each with a required capital (cost) and a profit. You can complete at most k projects sequentially. After completing a project, your capital increases by its profit. Maximize you…

• Strategy Using Two Heaps

  1. Min-heap by cost: all projects sorted by their capital requirement 2. Max-heap by profit: projects you can currently afford ---

• Common Pitfalls

• 1. Forgetting to Handle Empty Heaps

  When the first element arrives, there is no root to compare against. Always check if the max-heap is empty before comparing.

• 2. Off-by-One in Balance Check

  The invariant is |sizediff| <= 1, not == 0. One heap can have exactly one more element (odd total count), and that is fine.

• 3. Negation Errors in Python

  When using negated values for the max-heap: - Push: heappush(maxheap, -num) - Peek: -maxheap[0] (negate back to get true value) - Pop: -heappop(maxheap) Forgetting to negate when comparing or returning causes subtle bugs.

• 4. Rebalancing After Lazy Deletion

  In sliding window problems, the "effective size" (actual minus lazily-deleted) must be used for balance decisions, not the raw heap length. ---

• Complexity Summary

  | Operation | Time | Space | |-----------|------|-------| | Add number (median finder) | O(log n) | O(n) | | Find median | O(1) | — | | Sliding window median | O(n log k) | O(k) | | Maximize capital | O(n log n + k log n) | O(n) | ---

• Pattern Recognition Checklist

  Ask yourself: 1. Do I need to find the median of a growing/changing dataset? 2. Am I partitioning elements into two groups based on value? 3. Do I need quick access to the boundary elements of each group? 4. Am I selecting from available…