🔍 Intuition

Hospital Emergency Room Analogy

Think of a heap like an ER triage desk. Patients arrive in any order, but the most critical patient always gets seen first — regardless of who arrived when.

Min-Heap = Lowest priority number = highest urgency. Patient #1 (critical) goes before Patient #99 (minor cut).
Max-Heap = Highest value = highest priority. Best score gets served first.

Key Insight

A heap doesn't sort everything — it only guarantees the min (or max) is always accessible instantly. That's why it's O(1) peek and O(log n) insert/delete. You sacrifice full ordering for lightning-fast extremes.

Use a heap when you repeatedly need the smallest or largest element from a dynamic dataset.

📘 Definition

Complete Binary Tree

All levels are fully filled except possibly the last, which is filled left to right.

1

3

2

7

5

4

6

Min-heap: every node ≤ its children

Heap Property

Property	Min-Heap	Max-Heap
Node vs children	parent ≤ children	parent ≥ children
Root value	Minimum element	Maximum element
Subtrees	Also min-heaps	Also max-heaps

A heap is NOT fully sorted. Siblings have no ordering relationship with each other.

📊 Min-Heap vs Max-Heap

Min-Heap

1

3

2

7

5

4

Root = 1 (minimum)
Python's default via heapq

Max-Heap

9

7

8

3

5

6

Root = 9 (maximum)
Use negation trick in Python

When to use which?

Use Min-Heap for	Use Max-Heap for
Dijkstra's shortest path	Kth largest element
Task scheduling (low priority #)	Top K frequent elements
Merge K sorted lists	Sliding window maximum
Median maintenance	Priority queue (max first)

🧩 Tree + Array Representation

Tree → Array mapping (0-indexed)

1

3

2

7

5

4

6

0

1

3

2

3

7

4

5

4

6

Index Formulas (0-indexed)

Relation	Formula	Example (node at i=1)
Left child	2*i + 1	2*1+1 = 3 → value 7
Right child	2*i + 2	2*1+2 = 4 → value 5
Parent	(i-1) // 2	(3-1)//2 = 1 → value 3

No pointers needed! The array IS the tree. This is why heaps use O(n) space with no overhead.

🐍 Python heapq Module

Key Functions

Function	What it does	Time
heapq.heappush(h, x)	Insert x into heap h	O(log n)
heapq.heappop(h)	Remove & return minimum	O(log n)
heapq.heapify(list)	Turn list into heap in-place	O(n)
heapq.nsmallest(k, it)	k smallest elements	O(n log k)
heapq.nlargest(k, it)	k largest elements	O(n log k)
heapq.heappushpop(h, x)	Push then pop (efficient)	O(log n)
h[0]	Peek at minimum	O(1)

Usage Examples

import heapq

# ── Basic usage ──────────────────────────
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)

print(h[0])          # 1  (peek min, O(1))
print(heapq.heappop(h)) # 1  (pop min, O(log n))

# ── heapify existing list ─────────────────
nums = [9, 4, 7, 1, 6]
heapq.heapify(nums)     # in-place, O(n)
print(nums)             # [1, 4, 7, 9, 6]

# ── nsmallest / nlargest ─────────────────
heapq.nsmallest(3, nums) # [1, 4, 6]
heapq.nlargest(2, nums)  # [9, 7]

Python's heapq only supports min-heap. For max-heap, negate values (see Max Heap tab).

⚙️ Operations (Interactive)

Step through: Insert (Bubble Up)

Inserting 2 into heap [1, 4, 3, 7, 9]

Press "Next Step" to begin.

Insert Algorithm

# 1. Add to end of array
# 2. Bubble Up: compare with parent
#    while node < parent: swap, go up
# Time: O(log n) — height of tree

def heappush(heap, val):
    heap.append(val)           # add to end
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] < heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

Heapify — O(n) explained

Why O(n) and not O(n log n)? Most nodes are near the bottom (short travel distance). Mathematically, the sum of all bubble-down distances converges to O(n).

# Start from last non-leaf → index n//2 - 1
# Sift-down each node toward root
def heapify(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

🔄 Max-Heap via Negation

The Trick

Python's heapq is always a min-heap. To simulate max-heap, negate all values on push and un-negate on pop.

Min-heap of [-9, -7, -5] = Max-heap of [9, 7, 5]

Pattern

import heapq

max_heap = []
# Push: negate the value
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -9)
heapq.heappush(max_heap, -3)

# Peek max: negate h[0]
print(-max_heap[0])        # 9

# Pop max: negate the result
print(-heapq.heappop(max_heap)) # 9

# ── With tuples (e.g., (freq, word)) ─────
freq_heap = []
for word, freq in {"a":3, "b":1, "c":5}.items():
    heapq.heappush(freq_heap, (-freq, word))

print(heapq.heappop(freq_heap))  # (-5, 'c') → freq=5

For tuples: only negate the comparison key (first element). The rest stays unchanged.

⚡ Complexity Table

Operation	Time	Why
Peek (min/max)	O(1)	Root is always at index 0
Insert (push)	O(log n)	Bubble up ≤ tree height
Delete min/max	O(log n)	Sift down from root
Build heap (heapify)	O(n)	Most nodes near leaves
Delete arbitrary	O(n)	Search O(n) + fix O(log n)
Search	O(n)	No ordering between siblings
Merge two heaps	O(n)	Concat + heapify
nsmallest(k, n)	O(n log k)	Maintain size-k heap

Space complexity

O(n)

Heap sort time

O(n log n)

Heap vs alternatives

Structure	Insert	Get Min	Delete Min
Sorted array	O(n)	O(1)	O(n)
Unsorted array	O(1)	O(n)	O(n)
BST (balanced)	O(log n)	O(log n)	O(log n)
Heap ✓	O(log n)	O(1)	O(log n)

🧠 Concept Check

Score0 / 0

💻 Practice Problems

Kth Largest Element

Medium

Find the kth largest element in an unsorted array. Strategy: maintain a min-heap of size k. If heap size exceeds k, pop the minimum. The root is your answer.

import heapq

def findKthLargest(nums, k):
    heap = []                      # min-heap of size k
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)    # remove smallest
    return heap[0]               # root = kth largest

# Dry run: nums=[3,2,1,5,6,4], k=2
# After: heap=[5,6] → return 5 ✓
# Time: O(n log k)  Space: O(k)

Top K Frequent Elements

Medium

Count frequencies, then use a min-heap of size k sorted by frequency.

from collections import Counter
import heapq

def topKFrequent(nums, k):
    freq = Counter(nums)            # {num: count}
    # min-heap: (freq, num)
    heap = []
    for num, cnt in freq.items():
        heapq.heappush(heap, (cnt, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for _, num in heap]

# nums=[1,1,1,2,2,3], k=2
# freq={1:3, 2:2, 3:1}
# heap=[(2,2),(3,1)] → return [2,1] ✓
# Time: O(n log k)  Space: O(n)

Merge K Sorted Lists

Hard

Use a min-heap to always pick the smallest node across all k lists.

import heapq

def mergeKLists(lists):
    heap = []
    # Seed heap with head of each list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    curr  = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

# Time: O(N log k)  where N = total nodes
# Space: O(k)  — heap holds at most k nodes

Include i (list index) as tiebreaker to avoid comparing ListNode objects.

🚀 Interview Tips & Patterns

Pattern Recognition

Reach for a heap when you see:

🔢 Top K / Kth smallest/largest 🔗 Merge K sorted structures 📊 Median from data stream 🗺 Shortest path (Dijkstra) 🔄 Running min/max 📅 Meeting rooms / scheduling 🪟 Sliding window extremes ⚖️ Balance two halves

Common Heap Templates

Pattern	Heap type	Size
Kth largest	Min-heap	k
Kth smallest	Max-heap	k
All K largest	Min-heap	k (root = kth)
Merge K lists	Min-heap	k heads
Median stream	2 heaps (max+min)	balanced

Gotchas to mention in interviews

Python's heapq is min-heap only — always mention negation for max-heap
Heap is NOT fully sorted — siblings have no order guarantee
heapify is O(n), NOT O(n log n)
Use tuples (priority, item) for custom ordering
For Dijkstra, lazy deletion is fine — just skip stale entries
heappushpop is faster than separate push + pop

Two-heap pattern for median: max-heap for lower half, min-heap for upper half. Keep sizes equal (or differ by 1). Median is the root(s).

Avoid using nsmallest/nlargest in interviews if k is large — prefer building and maintaining your own heap for clarity.