A hospital emergency room does not run on first-come-first-served. A fractured wrist that arrived at 9 am waits; a cardiac case that arrived at 9:40 goes straight in. The rule isn't arrival — it's urgency: whoever is most critical right now goes next.
Software needs this rule constantly: the OS picks the highest-priority task, a game loop processes the nearest event, Dijkstra's algorithm (coming in the Algorithms course) picks the closest unvisited city. The abstract need is called a priority queue. Today we build the structure that implements it beautifully: the heap — a tree that secretly lives inside an array.
What would we naturally do?
The workload: items keep arriving; again and again we ask "who's most urgent?" and serve them. Two obvious designs, both flawed in mirror-image ways:
| Approach | Insert | Serve the min | The pain |
|---|---|---|---|
| Unsorted list | O(1) — just append | O(n) — scan everything | every serve re-searches |
| Sorted list | O(n) — shift to keep order | O(1) — it's at the end | every insert re-shifts |
| Heap | O(log n) | O(log n), peek O(1) | both cheap |
The unsorted list pays at read time; the sorted list pays at write time. Question: is full sortedness even needed? We never ask "who's third most urgent?" — we only ever need the one most extreme element. Keeping n items totally sorted, to read just the top one, is wasted work.
The observation: we over-sorted
So here's the design goal, stated precisely: maintain just enough order that the minimum is always instantly visible — and not one comparison more. Less order to maintain means cheaper inserts; enough order means instant peeks. The heap is exactly that compromise.
The heap property: order, but only vertically
A min-heap is a complete binary tree (every level full; the last level filled left to right) with one rule: every parent ≤ its children. That's all.
Notice what the rule does NOT say: nothing about left vs right, nothing comparing siblings or cousins. Order flows only vertically. But chase the rule upward from any node — parent ≤ me, grandparent ≤ parent... — and you reach the root, which is therefore ≤ everything. The minimum sits on top, readable in O(1), permanently. (A max-heap flips the inequality; everything mirrors.)
Is [2, 5, 3, 9, 6, 4] a valid min-heap? It's visibly unsorted — 5 before 3! But check the actual rule: 2 ≤ 5, 3 ✓; 5 ≤ 9, 6 ✓; 3 ≤ 4 ✓. Valid. A heap is NOT a sorted array — and that weakness is the feature we designed for.
A tree that lives in an array
Now the implementation elegance. Because the tree is complete — no gaps anywhere — we can pack it into a flat array, level by level, left to right. And then a small miracle: the parent-child links become arithmetic, exactly like the cinema-seat formula of lesson 2:
# 0-indexed array heap
# children of index i: 2*i + 1 and 2*i + 2
# parent of index i: (i - 1) // 2
heap = [2, 5, 3, 9, 6, 4]
# 0 1 2 3 4 5
# children of 1 (value 5): indices 3, 4 -> values 9, 6 OK: 5 <= both
# parent of 5 (value 4): index (5-1)//2 = 2 -> value 3 OK: 3 <= 4No Node class, no pointers, no per-node overhead — and the CPU cache loves the contiguity. A heap is the cheapest tree you will ever run.
Insert and extract: sift up, sift down
Both operations follow one philosophy: change the heap at an end (to keep completeness), then repair the single broken path.
Insert (sift up). Where can a new element go without leaving a gap? Only the next free slot at the end. It might be smaller than its parent — a rule violation — so swap it upward while it beats its parent. The violation travels up ONE path; at most height swaps: O(log n).
Extract-min (sift down). The answer is the root — take it. Now there's a hole on top. Which element can fill it without breaking completeness? Only the LAST element. Move it up — it's probably too big for the root, so swap it downward with its smaller child while a child beats it. Again one path, O(log n).
Student question: why the smaller child, specifically? Promote the bigger child and it becomes the parent of its smaller sibling — bigger above smaller, the rule breaks at the very spot you "fixed". The smaller child is the only safe promotion.
Dry run: extract-min, swap by swap
heap: [1, 3, 2, 7, 4, 5] extract-min -> answer is 1 move last element (5) to the root: [5, 3, 2, 7, 4] 5's children: 3 (idx 1) and 2 (idx 2); smaller child = 2 5 > 2 -> swap: [2, 3, 5, 7, 4] 5 now at idx 2; its children would be idx 5, 6 -> none exist sift-down ends. final: [2, 3, 5, 7, 4] check: 2<=3,5 3<=7,4 -> valid
Two rules make any sift-down trace mechanical: swap with the smaller child, stop when both children are ≥ you or you reach a leaf. Do one on paper and you own the operation.
heapq in practice
import heapq
nums = [7, 2, 19, 4, 25]
heapq.heapify(nums) # O(n)! - in place, min-heap
print(nums[0]) # peek min: O(1)
print(heapq.heappop(nums)) # extract min: O(log n)
heapq.heappush(nums, 1) # insert: O(log n)
print(nums[0])
# idiom 1 - max-heap: negate in, negate out
mx = [-x for x in [7, 2, 19]]
heapq.heapify(mx)
print(-heapq.heappop(mx)) # -> 19
# idiom 2 - priority queue of tasks: (priority, item) tuples
pq = []
heapq.heappush(pq, (2, "email backlog"))
heapq.heappush(pq, (1, "server down!"))
print(heapq.heappop(pq)) # tuples compare element-wiseResult
2 2 1 19 (1, 'server down!')
One genuinely surprising line up there: heapify is O(n), not O(n log n). The intuition: half of all elements are leaves and sift zero distance; a quarter sift one level; only one element can sift the full height. The costs shrink faster than the counts grow, and the total sums to O(n). Building by n pushes costs O(n log n) — heapify when you have all the data.
The top-K pattern (with a twist)
The heap's most-asked application: top 10 scores from a stream of 1 crore numbers, with tiny memory. Sorting needs all 1 crore in RAM. The heap answer keeps just 10 — but with a twist that trips everyone:
For the 10 LARGEST, keep a MIN-heap of size 10.
"Surely a max-heap for largest?" Think about what question you ask per arriving number: "does this beat the weakest member of my current top 10?" The weakest of the top 10 is the minimum of those 10 — so THAT is the element you need instant access to. Min-heap of the champions; its root is the entry bar:
import heapq
def top_k(stream, k):
heap = [] # min-heap of current champions
for x in stream:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]: # beats the weakest champion?
heapq.heapreplace(heap, x) # out with the weakest, in with x
return sorted(heap, reverse=True)
print(top_k([31, 8, 42, 7, 56, 23, 91, 15], 3))Result
[91, 56, 42]
O(n log k) time, O(k) memory — one pass with a 10-element structure against a crore-element stream. Mirror rule: top-K smallest → max-heap of size K. Say the reason out loud ("the root is the element on the bubble") and the interviewer knows you own it.
What if...?
What if I ask the heap for its 3rd smallest element? It shrugs. The second smallest is one of the root's two children, but the third could be a grandchild on either side — heap order is too weak to say. Finding the k-th smallest means k extractions (O(k log n)). A heap answers "most extreme", nothing else.
What if I need to search a heap for a value? O(n) scan — hashing's and BST's job, not the heap's. Ask a structure only the question it was built for.
What if the heap is empty and I pop? heapq.heappop raises IndexError — guard with if heap:, same discipline as stacks.
What if I must change an element's priority mid-flight (decrease-key)? heapq has no such operation. The standard workaround is lazy deletion: push the updated entry as a new tuple and skip stale ones when popped. That exact idiom powers Dijkstra in Python — you'll see it in the shortest-paths lesson.
Common mistakes
- Expecting the heap's array to be sorted, or iterating it for sorted output — pop repeatedly instead (that's literally heap sort).
- Mixing 0-indexed and 1-indexed formulas — state a convention and stick to it.
- Sifting down with the larger child.
- Max-heap of size k for top-k largest — it evicts your BEST element; the min-heap-of-champions is the right polarity.
- Building with n pushes when
heapify(O(n)) fits. - Using a heap where arbitrary search or ranges are needed — wrong question for this structure.
How do I recognise heap problems?
- "top K / K largest / K most frequent / K closest" → size-K heap, opposite polarity to the superlative.
- "always serve the most urgent / cheapest / nearest next" → priority queue = heap.
- "k-th largest in a stream" → the same size-k heap, kept alive between queries.
- "median of a stream" → two heaps facing each other (a Microsoft favourite — it's on the company pages).
- "merge k sorted lists" → heap of the k current front elements.
The counter-clue: "find / search / range" → not a heap. Heaps answer superlatives, not locations.
Quick revision
| Operation | Cost | Why |
|---|---|---|
| Peek min/max | O(1) | it's the root |
| Insert | O(log n) | sift up one path |
| Extract | O(log n) | last element to root, sift down |
| Heapify n items | O(n) | most elements sift almost nowhere |
| Search / k-th | O(n) / O(k log n) | not the heap's job |
No average/worst gap — completeness forces height ⌊log₂ n⌋, always. Space: O(n), one flat array, zero pointers.
One thing to remember
A heap keeps the minimum order needed to keep the extreme on top — don't ask it anything except "who's next?"
Practice Zone — PYQs from real selection rounds
Six MCQs, then three tasks: top-K with the heap traced, a sift-down by hand, and merging k sorted lists.
The min-heap property says:
Asked in
A heap stored in an array (0-indexed): the children of the node at index i are at:
Asked in
Extract-min on a heap of n elements costs O(log n) because:
Asked in
To find the 10 largest values in a stream of 1 crore numbers using little memory, you keep:
Asked in
Python's heapq gives you a min-heap. The standard way to get max-heap behaviour is:
Asked in
Is [2, 5, 3, 9, 6, 4] a valid min-heap?
Asked in
Hands-on tasks:
Find the 3 largest values of [7, 2, 19, 4, 25, 11, 8] with a size-3 min-heap. Trace the heap contents after each of the last three numbers.
Asked in
A min-heap array is [1, 3, 2, 7, 4, 5]. Extract-min once and show the array after each swap of the sift-down.
Asked in
Merge 3 sorted lists — [1, 5, 9], [2, 6], [3, 7, 8] — into one sorted list in O(n log k), k = number of lists, using a heap.
Asked in
FAQ
Heap vs BST — both trees; when which?
Heap: only the extreme matters — cheaper (flat array, O(1) peek, O(n) build). BST: order queries matter — ranges, successor, sorted iteration, k-th smallest — which a heap cannot answer without dismantling itself. "Priority queue → heap; ordered dictionary → BST" settles most cases.
What is heap sort, in one paragraph?
Heapify the array (O(n)), then extract the extreme n times (O(log n) each): O(n log n) total, in place, never quadratic. In practice quicksort's cache behaviour usually wins, so heap sort is mostly the answer to "name an in-place O(n log n) worst-case sort" — details in the sorting lesson.
Why must a heap be a complete tree?
Completeness is what makes the array form gapless and the height exactly ⌊log₂ n⌋. Allow holes and you'd need pointers back, and the height guarantee — the O(log n) bound itself — would depend on luck, like the plain BST's did.
How does the (priority, item) tuple trick handle ties?
Tuples compare element-wise, so equal priorities fall through to comparing the items — which crashes if items aren't comparable. The standard fix is a counter as tie-breaker: (priority, count, item). Worth knowing before it bites in a live round.
The urgency structure is yours. Next, we drop hierarchy entirely — anything connected to anything — Lesson 9: Graphs & Representations →