Advanced Heap Problems

🏆 Advanced Heap Problems: Becoming a Heap Master!

The Magic Mailroom Analogy: Imagine you work in a magical mailroom where letters keep arriving from different countries. Your job? Keep everything organized so you can always find the most important letter instantly!

🌟 What Are Advanced Heap Problems?

Think of a heap like a magic sorting hat from Harry Potter. Regular problems ask the hat to just find the biggest or smallest thing. But advanced problems? They ask the hat to do circus tricks!

Today, we’ll learn four amazing tricks:

1. 📬 Merge K Sorted Lists - Combining many sorted mailbags into one
2. 📊 Median from Data Stream - Finding the middle kid in a growing line
3. ⚖️ Two Heaps Pattern - Using two magic hats together
4. 🔤 Reorganize String - Spacing out repeat letters like arranging kids in class

📬 1. Merge K Sorted Lists

The Story

Imagine you have 5 mailbags, each already sorted by importance. Your job is to combine them into ONE perfectly sorted pile.

The Problem: You could dump all letters on the floor and re-sort everything. But that’s slow and messy! There’s a smarter way.

The Magic Trick: Min-Heap to the Rescue!

Think of a min-heap as a tiny trophy podium that only holds the top letter from each bag.

Bag 1: [1, 4, 5]
Bag 2: [1, 3, 4]
Bag 3: [2, 6]

Min-Heap (podium):
     1 ← smallest always on top!
    / \
   1   2

How it works:

1. Put the FIRST letter from each bag on the podium
2. Take the smallest one (it’s always on top!)
3. Add to your final sorted pile
4. Put the NEXT letter from that same bag on podium
5. Repeat until all bags are empty!

The Code

function mergeKLists(lists) {
  // MinHeap compares by node value
  const heap = new MinHeap();

  // Step 1: Add first item from each list
  for (let list of lists) {
    if (list) heap.add(list);
  }

  const dummy = { next: null };
  let current = dummy;

  // Step 2: Keep taking smallest
  while (!heap.isEmpty()) {
    const smallest = heap.remove();
    current.next = smallest;
    current = current.next;

    // Step 3: Add next from same list
    if (smallest.next) {
      heap.add(smallest.next);
    }
  }

  return dummy.next;
}

Why This Works

K = number of lists. When K is small, this is MUCH faster!

📊 2. Median from Data Stream

The Story

You’re the line monitor at school. Kids keep joining a line, and the principal keeps asking: “Who’s in the MIDDLE?”

The Challenge: The line keeps growing! How do you quickly find the middle kid without counting everyone each time?

The Two Halves Trick

Imagine splitting the line into TWO groups:

• Left Half: Shorter kids (use Max-Heap to track the tallest of the short)
• Right Half: Taller kids (use Min-Heap to track the shortest of the tall)

Smaller Half (Max-Heap)    Bigger Half (Min-Heap)
        [3]                      [5]
       /   \                    /   \
      1     2                  8     9

The MEDIAN is between 3 and 5!
If odd count: take the top of the bigger heap
If even count: average both tops

The Rules

1. Balance Rule: Both halves should be equal (or differ by 1)
2. Order Rule: Everything in left ≤ Everything in right

The Code

class MedianFinder {
  constructor() {
    this.small = new MaxHeap(); // left half
    this.large = new MinHeap(); // right half
  }

  addNum(num) {
    // Always add to small first
    this.small.add(num);

    // Move biggest from small to large
    this.large.add(this.small.remove());

    // Balance: large can't be bigger
    if (this.large.size() > this.small.size()) {
      this.small.add(this.large.remove());
    }
  }

  findMedian() {
    if (this.small.size() > this.large.size()) {
      return this.small.peek();
    }
    return (this.small.peek() +
            this.large.peek()) / 2;
  }
}

Example Walkthrough

Add 5: small=[5], large=[] → median=5
Add 2: small=[2], large=[5] → median=3.5
Add 8: small=[5,2], large=[8] → median=5
Add 1: small=[2,1], large=[5,8] → median=3.5

⚖️ 3. Two Heaps Pattern

The Big Idea

The Two Heaps pattern is like having two teams of helpers:

• Max-Heap Team: Finds the biggest in their group instantly
• Min-Heap Team: Finds the smallest in their group instantly

Together, they solve problems that need to track BOTH ends!

When to Use Two Heaps?

The Pattern Template

class TwoHeaps {
  constructor() {
    this.maxHeap = new MaxHeap(); // smaller half
    this.minHeap = new MinHeap(); // larger half
  }

  add(num) {
    // 1. Decide which heap
    if (this.maxHeap.isEmpty() ||
        num <= this.maxHeap.peek()) {
      this.maxHeap.add(num);
    } else {
      this.minHeap.add(num);
    }

    // 2. Rebalance if needed
    this.balance();
  }

  balance() {
    // Max-heap can have at most 1 more
    if (this.maxHeap.size() >
        this.minHeap.size() + 1) {
      this.minHeap.add(this.maxHeap.remove());
    }
    // Min-heap can't have more
    if (this.minHeap.size() >
        this.maxHeap.size()) {
      this.maxHeap.add(this.minHeap.remove());
    }
  }
}

Visual: Two Heaps in Action

graph TD
    A["New Number Arrives"] --> B{Smaller than max-heap top?}
    B -->|Yes| C["Add to Max-Heap"]
    B -->|No| D["Add to Min-Heap"]
    C --> E{Check Balance}
    D --> E
    E -->|Unbalanced| F["Move top between heaps"]
    E -->|Balanced| G["Done!"]
    F --> G

🔤 4. Reorganize String

The Story

You’re arranging kids in a photo line. Rule: No two kids with the same shirt color can stand next to each other!

Example:

• "aab" → "aba" ✅ (a and a separated by b)
• "aaab" → "" ❌ (can’t separate 3 a’s with just 1 b)

The Greedy Strategy

Key Insight: Always place the most common letter next, as long as it wasn’t just placed!

Think of it like:

1. Count how many of each letter you have
2. Always pick the letter you have MOST of (that you didn’t just use)
3. Use a Max-Heap to always know the most common!

The Code

function reorganizeString(s) {
  // Count each character
  const count = {};
  for (let c of s) {
    count[c] = (count[c] || 0) + 1;
  }

  // Check if possible
  const maxCount = Math.max(...Object.values(count));
  if (maxCount > Math.ceil(s.length / 2)) {
    return ""; // Impossible!
  }

  // Build max-heap by count
  const heap = new MaxHeap();
  for (let [char, cnt] of Object.entries(count)) {
    heap.add({ char, cnt });
  }

  let result = "";
  let prev = null;

  while (!heap.isEmpty() || prev) {
    // Can't continue? Impossible!
    if (heap.isEmpty() && prev) return "";

    // Take most frequent
    const current = heap.remove();
    result += current.char;
    current.cnt--;

    // Add previous back (skipped one turn)
    if (prev) {
      heap.add(prev);
      prev = null;
    }

    // Hold current for next round
    if (current.cnt > 0) {
      prev = current;
    }
  }

  return result;
}

Example: “aaabb”

Initial: a=3, b=2

Round 1: Pick 'a' (most) → "a"
         Hold: {a:2}, Heap: [{b:2}]

Round 2: Pick 'b' → "ab"
         Return {a:2}, Hold: {b:1}

Round 3: Pick 'a' → "aba"
         Return {b:1}, Hold: {a:1}

Round 4: Pick 'b' → "abab"
         Return {a:1}, Hold: none

Round 5: Pick 'a' → "ababa" ✅

The Impossibility Rule

If any character appears more than ⌈length/2⌉ times, it’s IMPOSSIBLE!

Why? With 5 slots: _ _ _ _ _ You can only fit 3 of the same letter with gaps between!

🎯 Summary: When to Use What?

graph TD
    A["Heap Problem?"] --> B{Multiple sorted sources?}
    B -->|Yes| C["Merge K Sorted Lists"]
    B -->|No| D{Need middle element?}
    D -->|Yes| E["Median from Stream"]
    D -->|No| F{Track both extremes?}
    F -->|Yes| G["Two Heaps Pattern"]
    F -->|No| H{Arrange with spacing?}
    H -->|Yes| I["Reorganize String"]
    H -->|No| J["Basic Heap Problem"]

💪 You’ve Got This!

Remember:

• Merge K Lists: Little podium holding one from each list
• Median Stream: Split the line in half, track the middle
• Two Heaps: Max-heap for small side, min-heap for big side
• Reorganize: Always pick most common (that you didn’t just pick)

These patterns appear in TONS of interview questions. Master them, and you’ll feel like a coding wizard! 🧙‍♂️