Heap Fundamentals

🏔️ Heaps: Your Magic Priority Toybox

Imagine you have a special toybox where the BIGGEST toy always floats to the top!

🎯 What is a Heap?

Think of a heap like a pyramid of friends standing on each other’s shoulders.

The strongest friend always stands at the very top! Every friend below is slightly weaker than the one above them.

       🏆 STRONGEST (Boss)
      /              \
   💪 Strong       💪 Strong
   /    \          /    \
 🙂 OK  🙂 OK   🙂 OK  🙂 OK

Two Types of Heaps:

• Max Heap: Biggest number sits on top (like tallest kid in front row photo)
• Min Heap: Smallest number sits on top (like shortest kid in front row)

🧩 Heap Fundamentals

The Golden Rules

A heap follows two simple rules:

1. Shape Rule: Fill the tree level by level, left to right (like reading a book)
2. Heap Rule: Parent is always bigger (max) or smaller (min) than children

     90      ← Parent
    /  \
   80   70   ← Children (both smaller than 90!)

Heap as an Array

Here’s the magic trick! We store this pyramid as a simple list:

Array:  [90, 80, 70, 60, 50, 40, 30]
Index:   0   1   2   3   4   5   6

Finding Family Members:

• Parent of index i: (i - 1) // 2
• Left child of index i: 2 * i + 1
• Right child of index i: 2 * i + 2

Example:

# For index 1 (value 80):
parent = (1 - 1) // 2 = 0  # → 90
left   = 2 * 1 + 1 = 3     # → 60
right  = 2 * 1 + 2 = 4     # → 50

⚙️ Heap Core Operations

1. Heapify (Bubble Down) 🫧⬇️

When a parent breaks the rule, it “bubbles down” to its correct spot.

Like a heavy ball sinking in water!

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

2. Insert (Bubble Up) 🫧⬆️

Add new item at the bottom, then let it “bubble up” to its spot.

Like a helium balloon rising!

def insert(heap, value):
    heap.append(value)
    i = len(heap) - 1

    # Bubble up
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

3. Extract Max (Remove Top) 📤

Take the top item, put the last item on top, then heapify down.

def extract_max(heap):
    if not heap:
        return None

    max_val = heap[0]
    heap[0] = heap[-1]
    heap.pop()
    heapify(heap, len(heap), 0)
    return max_val

🏗️ Building Heap from Array

The Smart Way: Start from the middle and heapify backwards!

Why middle? Because leaves (last half) are already valid heaps!

def build_heap(arr):
    n = len(arr)
    # Start from last non-leaf node
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    return arr

Example:

Input:  [4, 10, 3, 5, 1]

Step 1: Heapify index 1 (10)
        Already valid!

Step 2: Heapify index 0 (4)
        4 < 10, so swap!

Result: [10, 5, 3, 4, 1]

Time Complexity: O(n) — Surprisingly fast!

📊 Heap Sort

The Clever Idea:

1. Build a max heap
2. Swap top (max) with last element
3. Shrink heap by 1, heapify the top
4. Repeat until sorted!

def heap_sort(arr):
    n = len(arr)

    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

    return arr

graph TD
    A["[90,80,70,60]"] --> B["Swap 90↔60"]
    B --> C["[60,80,70] + 90"]
    C --> D["Heapify: [80,60,70]"]
    D --> E["Swap 80↔70"]
    E --> F["[70,60] + 70,90"]
    F --> G["Continue..."]

Time: O(n log n) | Space: O(1) — In-place sorting!

🎯 Kth Largest Element

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

Method 1: Max Heap (Extract K times)

import heapq

def kth_largest_max(nums, k):
    # Python heapq is min-heap
    # Negate for max-heap behavior
    max_heap = [-x for x in nums]
    heapq.heapify(max_heap)

    for _ in range(k - 1):
        heapq.heappop(max_heap)

    return -heapq.heappop(max_heap)

Method 2: Min Heap of Size K (Better!)

Keep only K largest elements. The top is the Kth largest!

def kth_largest_min(nums, k):
    min_heap = nums[:k]
    heapq.heapify(min_heap)

    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heapreplace(min_heap, num)

    return min_heap[0]

Time: O(n log k) | Space: O(k)

🏆 Top K Elements Pattern

Pattern: When you need the K largest/smallest elements!

Top K Frequent Elements

def top_k_frequent(nums, k):
    from collections import Counter

    count = Counter(nums)
    # Use min heap of size k
    heap = []

    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)

    return [num for freq, num in heap]

Example:

nums = [1,1,1,2,2,3], k = 2
Frequencies: {1:3, 2:2, 3:1}
Top 2: [1, 2]  (most frequent!)

K Largest Elements

def k_largest(nums, k):
    return heapq.nlargest(k, nums)

📍 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 (comparing x² + y² works too!)

def k_closest(points, k):
    # Max heap by negative distance
    heap = []

    for x, y in points:
        dist = x * x + y * y
        heapq.heappush(heap, (-dist, [x, y]))
        if len(heap) > k:
            heapq.heappop(heap)

    return [point for dist, point in heap]

Example:

points = [[1,3], [-2,2], [5,8], [0,1]]
k = 2

Distances:
[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]]

graph TD
    A["K Closest Pattern"] --> B["Calculate Distance"]
    B --> C["Use Max Heap Size K"]
    C --> D["Keep K Smallest"]
    D --> E["Return Heap Contents"]

🚀 Python’s heapq Module

Python has a built-in heap helper!

import heapq

nums = [5, 2, 8, 1, 9]

# Build min heap (in-place)
heapq.heapify(nums)

# Add element
heapq.heappush(nums, 3)

# Remove smallest
smallest = heapq.heappop(nums)

# Peek (don't remove)
peek = nums[0]

# Top K shortcuts
top_3 = heapq.nlargest(3, nums)
bottom_3 = heapq.nsmallest(3, nums)

Remember: Python’s heapq is MIN heap only!

For max heap, negate values: push -x, get back -heap[0]

🎓 Quick Summary

When to Use Heaps?

✅ Finding K largest/smallest ✅ Priority scheduling ✅ Merging sorted lists ✅ Median finding ✅ Graph algorithms (Dijkstra’s)

🌟 Key Takeaways

1. Heap = Priority Queue — Best for “always get max/min” tasks
2. Array storage — No pointers needed, just math formulas
3. O(log n) operations — Fast insertions and deletions
4. Top K pattern — Use min heap of size K for K largest
5. Python tip — heapq is min heap; negate for max heap!

You’ve mastered the heap! Now go build something awesome! 🚀