CMD Guide
Home › DSA

Heap

Step 12 in the DSA path · 2 concepts · 9 problems

0 / 11 complete

📘 Learn Heap from zero

A heap is a binary tree kept in an array where every parent beats its children (max-heap: parent largest; min-heap: parent smallest), so the extreme element sits at the root and is readable in O(1), with push/pop in O(log n). Reach for a heap whenever you repeatedly need the smallest or largest of a changing set — top-K, merging K sorted lists, scheduling by priority, or running statistics over a stream. The canonical example is Find Median from a Data Stream: keep a max-heap for the lower half and a min-heap for the upper half so the median is always at the two roots.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — The two-heap invariant
lo = MAX-heap (lower half, root = largest of low)
hi = MIN-heap (upper half, root = smallest of high)

INVARIANTS we must always restore:
  (1) every value in lo  <=  every value in hi
  (2) size(lo) == size(hi)   OR   size(lo) == size(hi)+1

      lo (max-heap)        hi (min-heap)
      [   empty   ]        [   empty   ]
         root=-                root=-

Median rule:
  odd  total -> lo.root
  even total -> (lo.root + hi.root) / 2

We split the data so the two middle elements live at the two roots. Because lo holds the smaller half (largest on top) and hi holds the larger half (smallest on top), the median is always one peek (or two) away — no sorting needed. Stream to process: 5, 15, 1, 3.

Step 2 — Insert 5
add 5: lo empty -> push to lo, then rebalance.

  lo (max): [5]          hi (min): []
             ^root=5                 root=-

sizes: lo=1, hi=0  -> invariant (2) holds (lo = hi+1)
roots: lo.root=5  (no hi to compare) -> invariant (1) holds

total=1 (odd) -> median = lo.root = 5

First element goes to lo. With one element the lone value is trivially the median. The push is O(log n) and the peek that gives the median is O(1) — this is the whole point of using heaps here.

Step 3 — Insert 15 (push, then cross-balance)
15 <= lo.root(5)? no -> belongs in upper half, push to hi.

  lo (max): [5]          hi (min): [15]
             ^root=5                 ^root=15

Check invariant (1): lo.root(5) <= hi.root(15)  OK
Check invariant (2): lo=1, hi=1  -> equal, OK

total=2 (even) -> median = (5 + 15)/2 = 10

Each new value is routed by comparing to lo's root: anything not <= it goes to the upper heap. Because the roots already satisfy lo.root <= hi.root and sizes are equal, no rebalance is needed — the invariants are safe.

Step 4 — Insert 1 (push to lo)
1 <= lo.root(5) -> belongs in lower half, push to lo.

  lo (max): [5,1]        hi (min): [15]
            root=5                  ^root=15
            sift: 1<5, stays child

      5            
     /             
    1              

sizes: lo=2, hi=1  -> lo is ahead by 1, still OK (lo = hi+1)
roots: lo.root(5) <= hi.root(15)  OK

total=3 (odd) -> median = lo.root = 5

1 is small, so it sinks into lo; the max-heap sift keeps 5 on top. Sizes are lo=2, hi=1, which is the allowed "lo leads by one" state, so the single middle element is exactly lo's root. Safe — no rebalance.

Step 5 — Insert 3: wrong-heap landing forces a rebalance
3 <= lo.root(5) -> push to lo first.

  lo (max): [5,1,3]      hi (min): [15]
      5
     / \
    1   3      sizes: lo=3, hi=1  <-- VIOLATES invariant (2)!
               (lo leads by 2, allowed max is 1)

The naive push overfills lo. Whenever size(lo) > size(hi)+1 we must move lo's root across to hi — this is the rebalance step that keeps the two halves the same size.

Step 6 — Rebalance: pop lo.root, push it to hi
pop max from lo (=5), push 5 into hi.

  lo (max): [3,1]        hi (min): [5,15]
      3                       5
     /                       \
    1                         15

WHY this is safe:
 - 5 was the LARGEST of the low half, so it is <= everything
   already in hi -> invariant (1) still holds (3 <= 5).
 - sizes now lo=2, hi=2  -> invariant (2) holds.

total=4 (even) -> median = (lo.root + hi.root)/2
               = (3 + 5)/2 = 4

Moving lo's root is always legal because it was the boundary value — the biggest of the small half is the smallest thing that can join the big half. Each transfer is O(log n), and after it the two roots straddle the true median: sorted data is 1,3,5,15 → median (3+5)/2 = 4.

Step 7 — General insert algorithm (the reusable template)
function addNum(x):
   if lo empty OR x <= lo.root:  lo.push(x)
   else:                         hi.push(x)

   # rebalance sizes (lo may lead by at most 1)
   if size(lo) > size(hi)+1:  hi.push(lo.popMax())
   elif size(hi) > size(lo):  lo.push(hi.popMin())

function findMedian():
   if size(lo) > size(hi):  return lo.root
   else:                    return (lo.root + hi.root)/2

Cost: addNum O(log n), findMedian O(1)

The whole pattern reduces to: route by comparison, then restore the size invariant by shuffling one root across. Replaying 5,15,1,3 through this gives running medians 5 → 10 → 5 → 4, exactly matching our trace — the heap roots are the streaming median for free.

🎯 Guided practice

Problem 1 (easy) — "Take Gifts From the Richest Pile" (greedy-with-a-heap). Given gift piles [25, 64, 9, 4, 100], repeat 4 times: take the richest pile, replace it with floor(sqrt(pile)), put it back. Return the total remaining.

  1. Recognize the signal: "repeatedly take the largest, modify, reinsert" → priority queue. We need the max each round over changing data → a max-heap.
  2. Build: heapify all gifts into a max-heap in O(n) (in most languages: negate values into a min-heap). Heap = {100,64,25,9,4}.
  3. Round 1: pop 100, push floor(sqrt(100))=10. Round 2: pop 64, push 8. Round 3: pop 25, push 5. Round 4: heap is {10,9,8,5,4}, pop 10, push 3.
  4. Result: remaining heap holds {9,8,5,4,3} → sum = 29. Each round is one pop + one push = O(log n); total O(n + k log n), space O(n). Lesson: the heap silently re-orders after every mutation, so the next "max" is always one peek away.

Problem 2 (medium) — Find the Median of a Number Stream (Two Heaps). Numbers arrive one at a time; after each, report the median. Stream: 5, 2, 8, 1.

  1. Recognize the signal: "running median over a stream" → the Two Heaps pattern. Keep a max-heap lo for the smaller half and a min-heap hi for the larger half, with the median at their seam.
  2. Invariant: every element in lo ≤ every element in hi, and 0 ≤ size(lo) - size(hi) ≤ 1. To add x: push x onto lo, move lo's max to hi, then if hi is now larger than lo, move hi's min back to lo. This keeps both halves correctly split at the seam.
  3. Trace (heaps shown as multisets). Add 5: lo={5}, hi={}. Median = 5. Add 2: lo={2}, hi={5}. Median = (2+5)/2 = 3.5. Add 8: lo={2,5}, hi={8}. Median = top of lo = 5. Add 1: lo={1,2}, hi={5,8}. Median = (2+5)/2 = 3.5.
  4. Read the median in O(1): if lo is larger, it's lo's root; if sizes are equal, average the two roots. Insert is O(log n) (rebalancing is a constant number of heap ops); space O(n). Lesson: when one extreme isn't enough but the middle is, two opposing heaps turn an O(n) median scan into O(log n) per element.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard
What signals in a problem tell you to reach for a heap, and what does a heap give you?
tap to reveal →
Reach for a heap whenever you repeatedly need the smallest or largest element of a changing set — e.g. top-K, merging K sorted lists, scheduling by priority, or running statistics over a stream. A heap is a complete binary tree (kept in an array) where every parent beats its children, so the extreme element sits at the root: peek is O(1), push/pop are O(log n).
💡 "Repeatedly take the extreme of a changing set" → heap.
Flashcard
How is a heap stored in an array, and what are the parent/child index formulas?
tap to reveal →
A heap is stored by level-order (breadth-first) traversal in an array, so no pointers are needed. For a node at index i: left child = 2i+1, right child = 2i+2, parent = (i-1)/2 (integer division).
💡 Left 2i+1, Right 2i+2, Parent (i-1)/2.
Flashcard
How do insertion (heapify up) and root deletion (heapify down) work, and what are their complexities?
tap to reveal →
Insert: place the new element at the end of the array, then heapify up (percolate up) — swap with its parent while it violates the heap property until it reaches its spot or the root. Delete: remove the root, move the last element to the root, then heapify down — swap with the larger/smaller child until the property is restored. Both run in O(log n) since the tree height is log n; peek of the root is O(1).
💡 Insert at end → bubble up; delete root → last-to-top → sink down.
Flashcard
What is the Two Heaps pattern for the running median of a stream, and what does each heap hold?
tap to reveal →
Keep a max-heap 'lo' for the smaller half and a min-heap 'hi' for the larger half. Invariants: every value in lo <= every value in hi, and sizes differ by at most 1 (lo may lead by one). To add x: push to lo if x <= lo.root else to hi, then rebalance by moving one root across. Median = lo.root when sizes differ, else average of the two roots. addNum is O(log n), findMedian is O(1).
💡 Max-heap low half + min-heap high half; median sits at the seam.
Flashcard
For 'Minimum Cost to Connect Sticks', what is the strategy and why does it work?
tap to reveal →
Put all stick lengths in a min-heap, then repeatedly pop the two shortest, combine them (cost = their sum, added to a running total), and push the combined stick back — until one stick remains. Always combining the two smallest ensures larger sticks are summed into the total fewer times, giving the minimum cost. Each round is two pops and one push, each O(log n).
💡 Greedy + min-heap: always fuse the two cheapest sticks (Huffman-style).
Flashcard
How does a max-heap solve 'Sort Characters by Frequency'?
tap to reveal →
First count each character's frequency in a hashmap. Then build a max-heap of (character, frequency) pairs keyed on frequency. Repeatedly pop the top (most frequent) character and append it to the result that many times until the heap is empty, producing characters in descending frequency order. The max-heap gives efficient retrieval of the current most-frequent character.
💡 Count → max-heap by freq → pop-and-append.
Flashcard
What heap-based greedy approach rearranges a string so no two identical characters are adjacent, and when is it impossible?
tap to reveal →
Count frequencies and put them in a max-heap. Each step, append one occurrence of the highest-frequency character, but hold it out of the heap; re-insert the previous step's character (with frequency decremented) only after placing the current one — this keeps identical characters from being adjacent. If you cannot place all characters this way, no valid arrangement exists (return "").
💡 Place most-frequent first, delay re-inserting the last-used char by one step.
Q1. For a node at index i in an array-based heap, where are its left child, right child, and parent?
Q2. What are the time complexities of peeking the extreme element versus inserting/deleting in a heap?
Q3. In the Two Heaps median solution, after inserting a number you find size(lo) (max-heap) exceeds size(hi) (min-heap) by 2. What restores the invariant?
Q4. For 'Minimum Cost to Connect Sticks' with input [1, 8, 2, 5], what is the minimum total cost?
Q5. Which data structure does the lesson use to solve 'K-th Smallest Prime Fraction' efficiently?
Q6. How does the max-heap approach decide a string CANNOT be rearranged so no two identical characters are adjacent?