Heap Fundamentals

🏔️ Heaps: The VIP Line at the Amusement Park

Imagine you’re at an amusement park. There’s a special line where the most important person (maybe the tallest kid, or the one with the most tickets) always stands at the front. No matter who joins the line, the most important person magically moves to the front!

That’s exactly what a Heap does with data. It’s a special way to organize things so the biggest (or smallest) is always easy to find.

🎢 What is a Heap?

A heap is like a family tree where parents follow a simple rule:

Max Heap: Every parent is bigger than their children. Min Heap: Every parent is smaller than their children.

       90         ← The king (biggest)
      /  \
    75    60      ← Parents bigger than kids
   /  \   /
  50  40 30       ← The little ones

Think of it this way:

• Max Heap = Tallest person always at the top
• Min Heap = Shortest person always at the top

🧩 Heap as an Array

Here’s the magic trick! We can store this tree in a simple list:

// The tree above as an array:
int[] heap = {90, 75, 60, 50, 40, 30};
//            0   1   2   3   4   5  ← positions

Finding Family Members:

• Parent of position i → (i - 1) / 2
• Left child of i → 2 * i + 1
• Right child of i → 2 * i + 2

Example: Position 1 (value 75)

• Parent: (1-1)/2 = 0 → 90 ✓
• Left child: 2*1+1 = 3 → 50 ✓
• Right child: 2*1+2 = 4 → 40 ✓

⚙️ Heap Core Operations

1️⃣ Peek: Who’s the VIP?

The VIP (biggest or smallest) is always at position 0. Just look there!

public int peek() {
    return heap[0];  // O(1) - instant!
}

2️⃣ Insert: New Person Joins

When someone new arrives:

1. They join at the end of the line
2. They bubble up until they find their right spot

// Insert 85 into our heap
// Before: {90, 75, 60, 50, 40, 30}
// After:  {90, 75, 85, 50, 40, 30, 60}
//              ↑   ↑
//         85 bubbled up past 60!

graph TD
    A["New value joins at end"] --> B["Compare with parent"]
    B --> C{Bigger than parent?}
    C -->|Yes| D["Swap with parent"]
    D --> B
    C -->|No| E["Done! Found your spot"]

Bubble Up Code:

void bubbleUp(int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[index] > heap[parent]) {
            swap(index, parent);
            index = parent;
        } else break;
    }
}

3️⃣ Remove: VIP Leaves

When the top person leaves:

1. Move the last person to the front
2. They bubble down until they find their spot

// Remove 90 (the max)
// Step 1: {30, 75, 60, 50, 40}
//          ↑ 30 moved to top
// Step 2: {75, 30, 60, 50, 40}
//          30 swaps with bigger child
// Step 3: {75, 50, 60, 30, 40}
//          Done! 30 found its spot

Bubble Down Code:

void bubbleDown(int index) {
    int size = heap.length;
    while (true) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;

        if (left < size &&
            heap[left] > heap[largest])
            largest = left;
        if (right < size &&
            heap[right] > heap[largest])
            largest = right;

        if (largest == index) break;
        swap(index, largest);
        index = largest;
    }
}

🏗️ Building Heap from Array

You have a messy room (unsorted array). How do you organize it into a heap?

The Smart Way (Bottom-Up): Start from the middle and heapify backwards!

int[] mess = {30, 10, 80, 20, 60, 50};

// Start from middle (index 2), go left
// heapify(2): 80 is fine
// heapify(1): 10 → swap with 60
// heapify(0): 30 → swap with 80

// Result: {80, 60, 50, 20, 10, 30}

void buildHeap(int[] arr) {
    int n = arr.length;
    // Start from last non-leaf node
    for (int i = n/2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

Why start from middle? Leaves (last half) have no children. They’re already mini-heaps!

Time: O(n) - surprisingly fast! 🚀

🎯 Heap Sort: Sorting with Heaps

The Idea: Keep removing the biggest and put it at the end!

Step 1: Build max heap from array
Step 2: Swap max (top) with last element
Step 3: Shrink heap size by 1
Step 4: Bubble down the new top
Step 5: Repeat until done!

void heapSort(int[] arr) {
    int n = arr.length;

    // Build max heap
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extract elements one by one
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);    // Move max to end
        heapify(arr, i, 0); // Fix the heap
    }
}

Example:

[4, 10, 3, 5, 1]
↓ Build heap
[10, 5, 3, 4, 1]
↓ Swap & heapify
[5, 4, 3, 1, | 10]
[4, 1, 3, | 5, 10]
[3, 1, | 4, 5, 10]
[1, | 3, 4, 5, 10]
Done! Sorted! ✨

Time: O(n log n) - always!

🏆 Kth Largest Element

Problem: Find the 3rd largest number in [3, 2, 1, 5, 6, 4]

The Clever Trick: Use a Min Heap of size K!

public int findKthLargest(int[] nums, int k) {
    // Min heap of size k
    PriorityQueue<Integer> minHeap =
        new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        // Keep only k elements
        if (minHeap.size() > k) {
            minHeap.poll(); // Remove smallest
        }
    }

    return minHeap.peek(); // Kth largest!
}

Why does this work?

• We keep only K largest elements
• Smallest of those K = Kth largest overall!

Example (k=3):

Add 3: heap = [3]
Add 2: heap = [2, 3]
Add 1: heap = [1, 2, 3]
Add 5: heap = [2, 3, 5] (removed 1)
Add 6: heap = [3, 5, 6] (removed 2)
Add 4: heap = [4, 5, 6] (removed 3)
Answer: 4 (3rd largest) ✓

Time: O(n log k)

🎁 Top K Elements Pattern

Problem: Find the K largest (or smallest, or most frequent) items.

Top K Largest

public int[] topKLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap =
        new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k)
            minHeap.poll();
    }

    // minHeap now has K largest
    int[] result = new int[k];
    for (int i = 0; i < k; i++)
        result[i] = minHeap.poll();
    return result;
}

Top K Frequent

// Find k most frequent elements
public int[] topKFrequent(int[] nums, int k) {
    // Count frequencies
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums)
        freq.put(n, freq.getOrDefault(n, 0) + 1);

    // Min heap by frequency
    PriorityQueue<Integer> heap =
        new PriorityQueue<>(
            (a, b) -> freq.get(a) - freq.get(b)
        );

    for (int num : freq.keySet()) {
        heap.offer(num);
        if (heap.size() > k) heap.poll();
    }

    // Extract results
    int[] result = new int[k];
    for (int i = 0; i < k; i++)
        result[i] = heap.poll();
    return result;
}

Pattern Rule:

• Top K largest → Use Min Heap of size K
• Top K smallest → Use Max Heap of size K
• Keep removing the “worst” to keep the “best”!

📍 K Closest Points to Origin

Problem: Find K points closest to (0, 0).

Distance Formula: √(x² + y²) But we can skip the √ for comparison!

public int[][] kClosest(int[][] points, int k) {
    // Max heap by distance (keep smallest)
    PriorityQueue<int[]> maxHeap =
        new PriorityQueue<>((a, b) ->
            (b[0]*b[0] + b[1]*b[1]) -
            (a[0]*a[0] + a[1]*a[1])
        );

    for (int[] point : points) {
        maxHeap.offer(point);
        if (maxHeap.size() > k)
            maxHeap.poll(); // Remove farthest
    }

    return maxHeap.toArray(new int[k][2]);
}

Example:

Points: [[1,3], [-2,2], [5,8], [0,1]]
K = 2

Distances (squared):
[1,3]  → 1+9 = 10
[-2,2] → 4+4 = 8
[5,8]  → 25+64 = 89
[0,1]  → 0+1 = 1

Closest 2: [[0,1], [-2,2]] ✓

Time: O(n log k)

🎯 Quick Reference

Java PriorityQueue

// Min Heap (default)
PriorityQueue<Integer> minHeap =
    new PriorityQueue<>();

// Max Heap
PriorityQueue<Integer> maxHeap =
    new PriorityQueue<>(
        Collections.reverseOrder()
    );

// Custom comparator
PriorityQueue<int[]> custom =
    new PriorityQueue<>((a, b) ->
        a[0] - b[0]  // By first element
    );

🧠 When to Use Heaps

✅ Use a heap when:

• You need the min/max quickly
• Finding K largest/smallest elements
• Scheduling tasks by priority
• Merging sorted lists
• Streaming data (running median)

❌ Don’t use a heap when:

• You need to search for any element
• Order matters (use sorted array)
• You need to update random elements

🎉 You Did It!

You now understand heaps - the VIP line of data structures! Remember:

1. Heap = Complete binary tree with parent-child ordering
2. Array magic makes it super efficient
3. Bubble up for insert, bubble down for remove
4. Top K pattern = Use opposite heap type!

Go build something awesome! 🚀