Heap Fundamentals

Heaps: Your Priority Kingdom 🏰

Imagine you’re the ruler of a magical kingdom where everyone wants to talk to you. But you’re smart! You don’t talk to just anyone first—you always meet the most important person first. That’s exactly what a Heap does with data!

🎯 What is a Heap?

A heap is like a special tree where the boss sits at the top!

Think of it like a pyramid of importance:

• The king (most important) always sits at the very top
• Everyone else sits below in levels
• Parents are always more important than their children

       KING (10)          ← Top = Most Important
      /        \
   Duke(8)   Earl(7)      ← Level 2
   /    \      /
Guard Guard Guard         ← Level 3
(5)   (3)   (2)

Two Types of Heaps

Simple Rule:

• Max Heap: Big boss on top
• Min Heap: Little helper on top

🛠️ Heap Core Operations

The Three Magic Powers

1. 📥 INSERT (Add Someone New)

When a new person joins the kingdom:

// Adding number 15 to our heap
// Step 1: Put at bottom
// Step 2: Bubble UP if bigger than parent

function insert(heap, value) {
  heap.push(value);        // Add at end
  bubbleUp(heap);          // Float up!
}

function bubbleUp(heap) {
  let i = heap.length - 1;
  while (i > 0) {
    let parent = Math.floor((i-1)/2);
    if (heap[i] <= heap[parent]) break;
    [heap[i], heap[parent]] =
      [heap[parent], heap[i]];
    i = parent;
  }
}

Like a bubble in water 🫧 — light things float up!

2. 📤 EXTRACT (Remove the Boss)

When the king leaves, we need a new king:

function extractMax(heap) {
  if (heap.length === 0) return null;
  const max = heap[0];      // Save the king
  heap[0] = heap.pop();     // Last person → top
  bubbleDown(heap, 0);      // Sink to place
  return max;
}

function bubbleDown(heap, i) {
  const n = heap.length;
  while (true) {
    let largest = i;
    let left = 2*i + 1;
    let right = 2*i + 2;
    if (left < n && heap[left] > heap[largest])
      largest = left;
    if (right < n && heap[right] > heap[largest])
      largest = right;
    if (largest === i) break;
    [heap[i], heap[largest]] =
      [heap[largest], heap[i]];
    i = largest;
  }
}

Like a stone in water 🪨 — heavy things sink down!

3. 👀 PEEK (Who’s the Boss?)

Just look at the top, don’t remove anyone:

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

🏗️ Building a Heap from Array

The Slow Way: Insert one by one → O(n log n)

The Smart Way: Heapify! → O(n)

function buildHeap(arr) {
  // Start from last parent, go backwards
  const start = Math.floor(arr.length/2) - 1;

  for (let i = start; i >= 0; i--) {
    bubbleDown(arr, i);
  }
  return arr;
}

// Example:
// [3, 1, 6, 5, 2, 4]
//        ↓
// [6, 5, 4, 1, 2, 3]  ← Max Heap!

graph TD
    A["Array: [3,1,6,5,2,4]"] --> B["Start at index 2"]
    B --> C["Fix node 6 ✓"]
    C --> D["Fix node 1 → swap with 5"]
    D --> E["Fix node 3 → swap with 6"]
    E --> F["Result: [6,5,4,1,2,3]"]

Why start from middle? Leaves (bottom half) have no children to fix!

📊 Heap Sort

Sorting using a heap is like a talent show:

1. Build a max heap (biggest on top)
2. Extract the biggest → put at end
3. Repeat until empty

function heapSort(arr) {
  // Step 1: Build max heap
  buildHeap(arr);

  // Step 2: Extract and place
  for (let i = arr.length - 1; i > 0; i--) {
    // Swap max with last
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // Shrink heap, fix root
    heapifyDown(arr, 0, i);
  }
  return arr;
}

// [3,1,6,5,2,4]
// → Build: [6,5,4,1,2,3]
// → Sort:  [1,2,3,4,5,6]

🏆 Kth Largest Element

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

The Heap Trick: Use a min heap of size K!

function findKthLargest(nums, k) {
  // Min heap of size k
  const minHeap = new MinHeap();

  for (const num of nums) {
    minHeap.insert(num);
    // Keep only k elements
    if (minHeap.size() > k) {
      minHeap.extractMin();
    }
  }

  // Top of min heap = Kth largest!
  return minHeap.peek();
}

// k=3, nums=[3,2,1,5,6,4]
// Heap grows: [3] → [2,3] → [1,2,3]
// → [2,3,5] → [3,5,6] → [4,5,6]
// Answer: 4 (3rd largest)

Why min heap?

• It keeps the K largest numbers
• The smallest of those K is the Kth largest!

graph TD
    A["k=3, Array"] --> B["Min Heap Size 3"]
    B --> C["Smallest in heap"]
    C --> D["= Kth Largest!"]

🎯 Top K Elements Pattern

This pattern appears EVERYWHERE!

Template:

function topKPattern(items, k, compare) {
  const heap = new MinHeap(compare);

  for (const item of items) {
    heap.insert(item);
    if (heap.size() > k) {
      heap.extractMin();
    }
  }

  return heap.getAll();
}

// Top K Frequent Elements
function topKFrequent(nums, k) {
  // Count frequencies
  const freq = {};
  for (const n of nums) {
    freq[n] = (freq[n] || 0) + 1;
  }

  // Min heap by frequency
  const heap = [];
  for (const [num, count] of Object.entries(freq)) {
    heap.push({num, count});
    heapifyByCount(heap);
    if (heap.length > k) extractMin(heap);
  }

  return heap.map(x => x.num);
}

When to use Top K Pattern:

📍 K Closest Points to Origin

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

Distance formula: √(x² + y²)

But wait! We can skip the square root (just compare squared distances).

function kClosest(points, k) {
  // Max heap of size k
  // (closest = smallest distance,
  //  so max heap keeps k smallest)
  const maxHeap = [];

  const dist = (p) => p[0]*p[0] + p[1]*p[1];

  for (const point of points) {
    const d = dist(point);

    if (maxHeap.length < k) {
      pushMax(maxHeap, {point, d});
    } else if (d < maxHeap[0].d) {
      // Closer than farthest in heap
      popMax(maxHeap);
      pushMax(maxHeap, {point, d});
    }
  }

  return maxHeap.map(x => x.point);
}

// points = [[1,3],[-2,2],[5,8],[0,1]]
// k = 2
// Distances: 10, 8, 89, 1
// Answer: [[-2,2], [0,1]]

graph TD
    A["Points Array"] --> B["Calculate Distance²"]
    B --> C["Max Heap Size K"]
    C --> D["If closer than max"]
    D --> E["Replace max"]
    E --> F["K Closest Points"]

🧠 Quick Mental Model

┌─────────────────────────────────────┐
│         HEAP = PRIORITY LINE        │
├─────────────────────────────────────┤
│  Max Heap: VIPs first              │
│  Min Heap: Smallest first          │
├─────────────────────────────────────┤
│  Insert: Add → Bubble UP           │
│  Extract: Remove → Bubble DOWN     │
│  Peek: Just look at top            │
├─────────────────────────────────────┤
│  Kth Largest: Min heap, size K     │
│  K Closest: Max heap of distances  │
└─────────────────────────────────────┘

🚀 When to Use Heaps

🎉 You Made It!

You now understand:

• ✅ What heaps are (priority pyramids!)
• ✅ Insert, Extract, Peek operations
• ✅ Building heaps efficiently
• ✅ Heap Sort algorithm
• ✅ Finding Kth largest
• ✅ Top K pattern
• ✅ K Closest points

Remember: When you need to keep track of “the best K things” → Think Heap!

Go build something amazing! 🏗️