Advanced Heap Problems

🏔️ Advanced Heap Problems: Your Superpower Toolkit

Imagine you’re a superhero with a magical backpack that always gives you the most important item first. That’s what heaps do! Now let’s learn some super-cool tricks with them.

🧺 The Magic Basket Analogy

Think of heaps like two magic baskets:

• Max-Heap Basket: Always shows you the BIGGEST item on top
• Min-Heap Basket: Always shows you the SMALLEST item on top

Today, we’ll solve 4 amazing puzzles using these magic baskets!

📦 Problem 1: Merge K Sorted Lists

The Story

Imagine you have K different toy boxes, each with toys arranged from smallest to biggest. You want to combine ALL toys into ONE big line, still in order!

The Simple Idea

Instead of looking at ALL toys, just peek at the first toy from each box. Pick the smallest one, add it to your line, then look at the next toy from that box!

// Think of ListNode as a toy
// val = toy size, next = next toy

class ListNode {
    int val;
    ListNode next;
}

How It Works

graph TD
    A["Box 1: 1→3→5"] --> D["Min-Heap"]
    B["Box 2: 2→4→6"] --> D
    C["Box 3: 0→7→8"] --> D
    D --> E["Pick smallest: 0"]
    E --> F["Result: 0→1→2→3→..."]

The Java Solution

public ListNode mergeKLists(
    ListNode[] lists) {

    // Min-heap: smallest first
    PriorityQueue<ListNode> heap =
        new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );

    // Put first toy from each box
    for (ListNode node : lists) {
        if (node != null) {
            heap.offer(node);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (!heap.isEmpty()) {
        // Pick smallest
        ListNode smallest = heap.poll();
        current.next = smallest;
        current = current.next;

        // Add next toy from that box
        if (smallest.next != null) {
            heap.offer(smallest.next);
        }
    }

    return dummy.next;
}

Why This Works

Time: O(N log K) where N = total toys, K = boxes Space: O(K) for the heap

🎯 Problem 2: Find Median from Data Stream

The Story

You’re watching a number parade! Numbers keep marching in, one by one. At ANY moment, someone might ask: “What’s the middle number of everyone who passed?”

What’s a Median?

If you line up all numbers from small to big:

• Odd count: Pick the middle one
• Even count: Average of two middle ones

Example: [1, 3, 5] → median = 3 Example: [1, 3, 5, 7] → median = (3+5)/2 = 4

The Brilliant Trick: Two Heaps! 🎩

Split numbers into TWO groups:

• Left Half (smaller numbers) → Max-Heap (gives biggest of smalls)
• Right Half (bigger numbers) → Min-Heap (gives smallest of bigs)

graph LR
    subgraph Left["Left Half - Max Heap"]
        A["Shows: 3"]
        B["Hidden: 1, 2"]
    end
    subgraph Right["Right Half - Min Heap"]
        C["Shows: 4"]
        D["Hidden: 5, 6"]
    end
    A --> |"Median = #40;3+4#41;/2"| C

The Java Code

class MedianFinder {
    // Left half: max-heap
    PriorityQueue<Integer> left =
        new PriorityQueue<>(
            Collections.reverseOrder()
        );

    // Right half: min-heap
    PriorityQueue<Integer> right =
        new PriorityQueue<>();

    public void addNum(int num) {
        // Step 1: Add to left first
        left.offer(num);

        // Step 2: Balance - move max
        // of left to right
        right.offer(left.poll());

        // Step 3: Keep sizes equal
        // (left can have 1 extra)
        if (right.size() > left.size()) {
            left.offer(right.poll());
        }
    }

    public double findMedian() {
        if (left.size() > right.size()) {
            return left.peek();
        }
        return (left.peek() +
                right.peek()) / 2.0;
    }
}

Example Walkthrough

Time: O(log n) per add, O(1) for median Space: O(n)

⚖️ Problem 3: Two Heaps Pattern

The Pattern Explained

The Two Heaps pattern is like having two referees:

• One watches the smaller team (Max-Heap)
• One watches the bigger team (Min-Heap)

Together, they help you track the middle ground!

When To Use It

Use Two Heaps when you need to:

1. Find the median
2. Balance two groups
3. Track a sliding window’s middle
4. Partition data dynamically

Classic Example: Sliding Window Median

You have a window sliding across numbers. Find median of each window!

Array: [1, 3, -1, -3, 5, 3, 6, 7]
Window size: 3

Window [1,3,-1] → median = 1
Window [3,-1,-3] → median = -1
Window [-1,-3,5] → median = -1
...

Template Code

class TwoHeapsTemplate {
    PriorityQueue<Integer> maxHeap =
        new PriorityQueue<>(
            Collections.reverseOrder()
        );
    PriorityQueue<Integer> minHeap =
        new PriorityQueue<>();

    void addNumber(int num) {
        // Always try maxHeap first
        if (maxHeap.isEmpty() ||
            num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        rebalance();
    }

    void removeNumber(int num) {
        if (num <= maxHeap.peek()) {
            maxHeap.remove(num);
        } else {
            minHeap.remove(num);
        }
        rebalance();
    }

    void rebalance() {
        // maxHeap can have at most
        // 1 extra element
        if (maxHeap.size() >
            minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        }
        if (minHeap.size() >
            maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    double getMedian() {
        if (maxHeap.size() ==
            minHeap.size()) {
            return (maxHeap.peek() +
                    minHeap.peek()) / 2.0;
        }
        return maxHeap.peek();
    }
}

Visual: The Balancing Act

graph TD
    subgraph Balance["Keep Balanced!"]
        A["Max-Heap Size"] --> C{Difference ≤ 1?}
        B["Min-Heap Size"] --> C
        C -->|Yes| D["Balanced!"]
        C -->|No| E["Move elements"]
        E --> C
    end

🔤 Problem 4: Reorganize String

The Story

You have letter tiles. You want to arrange them so no two same letters touch! Like seating kids who might fight if they sit together.

Example:

• Input: "aab" → Output: "aba" ✅
• Input: "aaab" → Output: "" ❌ (impossible!)

The Strategy

1. Count how many of each letter
2. Use Max-Heap to always pick the most frequent
3. Place it, then put it aside temporarily
4. Pick next most frequent, repeat!

When Is It Impossible?

If any letter appears more than (n+1)/2 times, impossible!

For "aaab" (length 4): max allowed = (4+1)/2 = 2 But ‘a’ appears 3 times → impossible!

The Java Solution

public String reorganizeString(
    String s) {

    // Count frequencies
    int[] count = new int[26];
    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }

    // Max-heap: most frequent first
    // Store: [count, char]
    PriorityQueue<int[]> heap =
        new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );

    for (int i = 0; i < 26; i++) {
        if (count[i] > 0) {
            // Check impossible case
            if (count[i] >
                (s.length() + 1) / 2) {
                return "";
            }
            heap.offer(
                new int[]{count[i], i}
            );
        }
    }

    StringBuilder result =
        new StringBuilder();

    while (heap.size() >= 2) {
        // Take two most frequent
        int[] first = heap.poll();
        int[] second = heap.poll();

        // Add both to result
        result.append(
            (char)(first[1] + 'a'));
        result.append(
            (char)(second[1] + 'a'));

        // Put back if still have more
        first[0]--;
        second[0]--;

        if (first[0] > 0) {
            heap.offer(first);
        }
        if (second[0] > 0) {
            heap.offer(second);
        }
    }

    // Handle last character
    if (!heap.isEmpty()) {
        result.append(
            (char)(heap.poll()[1] + 'a')
        );
    }

    return result.toString();
}

Example: “aaabb”

Time: O(n log k) where k = unique chars (max 26) Space: O(26) = O(1)

🎓 Quick Summary

💡 Remember These Tips!

1. Min-Heap = PriorityQueue (default in Java)
2. Max-Heap = Use Collections.reverseOrder()
3. Two Heaps = Perfect for “middle” problems
4. Greedy + Heap = Great for scheduling/arrangement

🚀 You Got This!

You’ve just learned some of the most powerful heap tricks used by top engineers! Practice these patterns, and you’ll see them everywhere:

• Sorting merged data? → Heap!
• Finding middle values? → Two Heaps!
• Rearranging with constraints? → Max-Heap + Greedy!

Happy Coding! 🎉