Advanced Heap Problems

🏔️ Advanced Heap Problems: The Magic Mountain Rescue Team

Imagine you’re the leader of a rescue team that uses magical mountains. These mountains can instantly tell you who needs help FIRST or who needs help LAST. Today, we’ll learn how pros use these mountains to solve super tricky problems!

🌟 The Big Picture

Remember how a heap is like a magical mountain?

• Max Heap: The BIGGEST item sits at the very top
• Min Heap: The SMALLEST item sits at the very top

Today’s advanced problems are like combining multiple mountains, or using mountains in clever ways nobody thought of before!

🔗 Problem 1: Merge K Sorted Lists

The Story

Imagine you have 5 different lines of kids at an ice cream shop. Each line is already sorted by height (shortest to tallest). You need to combine ALL kids into ONE perfectly sorted line.

The Silly Way: Look at ALL kids, find the shortest, add them. Repeat. SO SLOW!

The Smart Way: Use a mini-heap that only looks at the FIRST kid in each line!

How It Works

graph TD
    A["Line 1: 1→4→5"] --> H["Min Heap"]
    B["Line 2: 1→3→4"] --> H
    C["Line 3: 2→6"] --> H
    H --> D["Always pick<br>smallest first kid"]
    D --> E["Add to result<br>bring next from that line"]

The Magic Trick

1. Put the first item from each list into a min-heap
2. Pop the smallest (it goes to your result!)
3. Push the next item from that same list
4. Repeat until done!

Python Code

import heapq

def merge_k_lists(lists):
    # Min heap: (value, list_index, item_index)
    heap = []

    # Add first element from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, list_i, item_i = heapq.heappop(heap)
        result.append(val)

        # Push next item from same list
        if item_i + 1 < len(lists[list_i]):
            next_val = lists[list_i][item_i + 1]
            heapq.heappush(heap, (next_val, list_i, item_i + 1))

    return result

# Example
lists = [[1,4,5], [1,3,4], [2,6]]
print(merge_k_lists(lists))
# Output: [1, 1, 2, 3, 4, 4, 5, 6]

Why It’s Fast

• With K lists and N total items
• We only keep K items in the heap (one per list)
• Each push/pop is O(log K)
• Total: O(N log K) - WAY better than checking all items!

📊 Problem 2: Find Median from Data Stream

The Story

You’re running a video game tournament. Players keep joining, and after EACH new player, someone asks: “What’s the MIDDLE skill level right now?”

You can’t sort everyone every time - too slow! You need a magical system.

The Brilliant Idea: Two Mountains! 🏔️🏔️

Imagine splitting all players into two groups:

• Left Mountain (Max Heap): The SMALLER half. Top = biggest of the small ones
• Right Mountain (Min Heap): The BIGGER half. Top = smallest of the big ones

The median is always hiding at the TOP of one (or both) mountains!

graph TD
    subgraph Left["Max Heap - Small Half"]
        L1["Top: 3"]
        L2["2"]
        L3["1"]
    end
    subgraph Right["Min Heap - Big Half"]
        R1["Top: 5"]
        R2["7"]
        R3["9"]
    end
    L1 -.->|Median is between| R1

The Rules

1. Keep mountains balanced (same size, or left has 1 extra)
2. Left top ≤ Right top (small half’s biggest ≤ big half’s smallest)
3. Median = Left top (if odd count) or average of both tops (if even)

Python Code

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # Max heap (use negatives!)
        self.large = []  # Min heap

    def addNum(self, num):
        # Always add to small first (negate for max heap)
        heapq.heappush(self.small, -num)

        # Balance: small's max should <= large's min
        if self.large and -self.small[0] > self.large[0]:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)

        # Balance sizes: small can have at most 1 more
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        if len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

# Example
mf = MedianFinder()
mf.addNum(1)  # [1] → median = 1
mf.addNum(2)  # [1,2] → median = 1.5
print(mf.findMedian())  # 1.5
mf.addNum(3)  # [1,2,3] → median = 2
print(mf.findMedian())  # 2

The Secret

Each addNum is just O(log n) - push and maybe one rebalance. Finding median is O(1) - just peek at tops!

⚖️ Problem 3: The Two Heaps Pattern

The Story

The Two Heaps pattern is like having TWO special assistants:

• Max Heap Assistant: Tracks smaller elements, instantly knows the BIGGEST of them
• Min Heap Assistant: Tracks larger elements, instantly knows the SMALLEST of them

Together, they answer questions about the MIDDLE of your data!

When to Use Two Heaps

Ask yourself: “Do I need to track the DIVIDING LINE between small and big values?”

The Pattern Template

import heapq

class TwoHeapsPattern:
    def __init__(self):
        self.max_heap = []  # Left/smaller half (use negatives)
        self.min_heap = []  # Right/larger half

    def add(self, num):
        # Step 1: Add to appropriate heap
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)

        # Step 2: Rebalance if needed
        self._rebalance()

    def _rebalance(self):
        # Keep sizes equal or max_heap has 1 extra
        if len(self.max_heap) > len(self.min_heap) + 1:
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)
        elif len(self.min_heap) > len(self.max_heap):
            val = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -val)

Real Example: Sliding Window Median

def sliding_median(nums, k):
    # For each window of size k, find median
    # Uses Two Heaps + lazy removal
    pass  # Complex but uses same pattern!

Key Insight 💡

Two heaps give you O(1) access to the boundary between “small” and “big” - something sorting can’t do efficiently with streaming data!

🔤 Problem 4: Reorganize String

The Story

You’re arranging kids in a photo line, but siblings can’t stand next to each other! If you have “aab”, you can arrange it as “aba” (siblings separated), but “aaab” is IMPOSSIBLE (too many a’s!).

The Greedy Strategy

Always place the most common character next… but never the one you just placed!

The Magic Formula

graph TD
    A["Count all letters"] --> B["Put counts in Max Heap"]
    B --> C{Heap empty?}
    C -->|No| D["Pop most frequent"]
    D --> E["Add it to result"]
    E --> F["Save 'last used' aside"]
    F --> G["Push 'last used' back<br>if count > 0"]
    G --> C
    C -->|Yes| H["Done!"]

Impossible Check

If ANY character appears more than (n + 1) // 2 times, it’s IMPOSSIBLE!

Why? In “aaab” (length 4), ‘a’ appears 3 times. Max allowed = (4+1)//2 = 2. Impossible!

Python Code

import heapq
from collections import Counter

def reorganize_string(s):
    counts = Counter(s)

    # Check if possible
    max_count = max(counts.values())
    if max_count > (len(s) + 1) // 2:
        return ""  # Impossible!

    # Max heap: (-count, char)
    heap = [(-cnt, char) for char, cnt in counts.items()]
    heapq.heapify(heap)

    result = []
    prev = None  # Track what we just used

    while heap:
        cnt, char = heapq.heappop(heap)
        result.append(char)

        # Push back previous if it still has count
        if prev:
            heapq.heappush(heap, prev)
            prev = None

        # Save current as "used" (will push next round)
        if cnt + 1 < 0:  # Still has remaining count
            prev = (cnt + 1, char)

    return ''.join(result)

# Examples
print(reorganize_string("aab"))   # "aba"
print(reorganize_string("aaab"))  # "" (impossible)
print(reorganize_string("aabb"))  # "abab" or "baba"

Why Max Heap?

We ALWAYS want to use the most frequent character (if we can). The max heap gives us that character in O(1)!

🎯 Summary: When to Use Which Pattern

🧠 Quick Memory Tips

1. Merge K Sorted: “Only K items in heap, always pop smallest, push its neighbor”

2. Median Stream: “Two mountains facing each other, median is at the peaks”

3. Two Heaps Pattern: “Small numbers on left mountain (max heap), big on right (min heap)”

4. Reorganize String: “Always pick the busiest character, but never the same one twice in a row”

🚀 You’re Now a Heap Hero!

These patterns appear in:

• Database query optimization
• Real-time analytics dashboards
• Task schedulers
• Load balancers
• And many more production systems!

The secret? Heaps give you O(log n) insertions with O(1) access to extremes. When you need the biggest OR smallest (or both!) constantly… think HEAPS!

Keep practicing, and soon these patterns will feel like second nature. You’ve got this! 🎉