The Min-Heap: What It Is and Why Interviews Love It
- Min-heap invariant: every parent ≤ both children; the root always holds the global minimum
- Array storage: parent-child index math eliminates pointers; all relationships computed in O(1)
- O(log n) for insert and extract-min: insert sifts up, extract-min sifts down, both travel at most the tree height
- O(n) heapify: sift-down from the last non-leaf node outperforms n individual pushes
- Python max-heap trick: negate values before pushing into
heapq, un-negate on pop - Top-K smallest uses a max-heap of size K: the most-misapplied heap pattern in interviews
- Heap is not sorted:
heap[1]is not necessarily the second-smallest; arbitrary search is O(n)
Every time you call heapq.heappush() in Python or grab a PriorityQueue in Java, you're using a min-heap. Most people never look inside. That's fine, until an interviewer asks you to implement one from scratch or you spend twenty minutes debugging why your top-K solution is returning the wrong elements. Get the mental model right and a whole class of problems (top-K, Dijkstra, streaming medians) becomes pattern recognition instead of guesswork.
The One Rule Everything Else Falls Out From
A min-heap is a complete binary tree with one constraint: every parent node is less than or equal to both of its children. That's it. That's the whole invariant.
Complete binary tree means filled level by level, left to right, no gaps. That completeness constraint is doing more work than it looks like.
The root always holds the minimum element. Not because we put it there manually, but because if any node were smaller than its parent, the heap property would break. Walk up from any leaf and values only increase.
Notice what the heap does NOT guarantee. The left child has no particular relationship to the right child. The second-smallest element could be in either subtree. This is a partial order, not a full sort. That's the key difference from a sorted array, and it's what makes heap operations fast.
heap[1] is not necessarily the second-smallest element. heap[2] might be. You'd have to check both. This surprises people in interviews. Don't be surprised.
Array Storage: The Part That Feels Like a Trick
A min-heap lives in a plain array. No pointers. No nodes. No left and right fields. Parent-child relationships fall out of index math.
For a node at index i:
- Left child:
2*i + 1 - Right child:
2*i + 2 - Parent:
(i - 1) // 2
The root sits at index 0, and every relationship is computable in O(1) with integer arithmetic. The "complete" constraint guarantees no gaps, so you can always append to the end and find the last element in O(1).
heap = [1, 3, 2, 7, 5, 4, 6] # 0 1 2 3 4 5 6 # heap[0] = 1 (root/min) # heap[0]'s children: heap[1]=3, heap[2]=2 # heap[1]'s children: heap[3]=7, heap[4]=5 # heap[2]'s children: heap[5]=4, heap[6]=6
The tree is just an illusion. The array is the real thing.
Insert Sifts Up
Append the new element to the end, then sift up: compare with the parent, swap if smaller, keep going until the heap property holds or you hit the root.
def heappush(heap, val): heap.append(val) 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
In the worst case, the new element is the new minimum and bubbles all the way from leaf to root. A complete binary tree with n nodes has height floor(log2(n)), so at most O(log n) swaps. The new element earns its position.
Extract-Min Sifts Down
Removing the minimum is the operation that makes heaps worth using. You can't just delete the root. I mean, you can try. The heap will disagree.
- Swap the root with the last element.
- Remove the last element (that's your minimum).
- Sift the new root down: swap with its smaller child until the heap property holds or it hits a leaf.
def heappop(heap): if len(heap) == 1: return heap.pop() min_val = heap[0] heap[0] = heap.pop() i = 0 n = len(heap) while True: left = 2 * i + 1 right = 2 * i + 2 smallest = i if left < n and heap[left] < heap[smallest]: smallest = left if right < n and heap[right] < heap[smallest]: smallest = right if smallest == i: break heap[i], heap[smallest] = heap[smallest], heap[i] i = smallest return min_val
The swap-with-last trick is what keeps the tree complete after deletion. Popping from the end costs O(1) and preserves the structure. The sift-down pass is at most O(log n).
Building from an Array Is O(n), Not O(n log n)
The naive approach: push each element one at a time. That's n pushes at O(log n) each, so O(n log n). There's a better way, and it comes up in interviews.
Heapify in-place in O(n): start at the last non-leaf node (index n//2 - 1) and call sift-down on every node moving toward the root.
def heapify(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): sift_down(arr, i, n)
Half the nodes are leaves and do zero work. A quarter are one level up and sift at most one level. Only the root ever travels the full height. When you sum the work across all nodes, it converges to O(n). This is one of those results that feels like it should be wrong until you work through the geometric series. Python's heapq.heapify() uses exactly this. Saying "heapify is O(n), not O(n log n)" in an interview signals that you've actually thought about this, not just used it.
Min Heap Time Complexity
| Operation | Time |
|---|---|
Peek min (heap[0]) | O(1) |
| Insert | O(log n) |
| Extract min | O(log n) |
| Build from array | O(n) |
| Search arbitrary element | O(n) |
Space is O(n). No overhead beyond the array itself.
Min-Heap vs Max-Heap: One Trick
A max-heap flips the invariant: every parent is greater than or equal to both children. The root holds the maximum.
Java's PriorityQueue is min-heap by default. Pass Collections.reverseOrder() for max. C++'s priority_queue is max-heap by default. Use std::greater<T> for min. Python's heapq is min-only. Always.
Python's max-heap trick: negate all values before inserting. Push -val instead of val, then negate again when you pop. It feels wrong. It works.
import heapq max_heap = [] for val in [3, 1, 4, 1, 5, 9]: heapq.heappush(max_heap, -val) max_val = -heapq.heappop(max_heap) # 9
Four Interview Patterns That Require a Heap
These patterns show up constantly. Each one is a min-heap problem in disguise, and recognizing the disguise is most of the work.
1. Top-K Smallest Elements
Counterintuitive, and this one catches people: use a max-heap of size K, not a min-heap of everything. Iterate through the array. If the current element is smaller than the heap's maximum, pop the max and push the current element. After processing all n elements, the heap holds the K smallest. O(n log k). The max-heap acts as a size-K eviction mechanism, not a collection mechanism. Sit with that for a second.
2. K-Way Merge
Given K sorted lists, merge them into one sorted output. Push the first element of each list into a min-heap tagged with its list index. Extract the minimum, push the next element from the same list. Repeat. You always pull the global minimum in O(log k) per step, regardless of total element count. This is how external sort works at scale.
3. Dijkstra's Shortest Path
Always relax the unvisited node with minimum current distance. That "always pick the minimum" requirement is exactly what a min-heap is for. Store (distance, node) pairs. Each extraction is O(log V), giving O((V + E) log V) overall.
4. Median of a Data Stream
Maintain two heaps: a max-heap for the lower half of values and a min-heap for the upper half. Keep them balanced in size (within 1). The median is either the root of the larger heap or the average of both roots. Both peek operations are O(1). Rebalancing after each insert is O(log n). This is a genuine senior-level interview favorite, and you'll know it's coming before the interviewer finishes the sentence.
If you want to practice these patterns under interview conditions, with voice-based feedback on your explanation and real-time hints, SpaceComplexity simulates realistic DSA interviews where you reason through heap problems out loud, not just write correct code in silence.
The Mistakes Everyone Makes Once
Wrong heap type for top-K. Top-K smallest uses a MAX-heap of size K. Top-K largest uses a MIN-heap of size K. The heap you maintain is the opposite type from what the problem asks for. Read that again. Slowly. This is the single most common heap interview mistake and it happens because the counterintuitive answer sounds wrong even when you know it's right.
Heapify vs a loop of heappush. heapq.heapify(arr) is O(n). Looping heapq.heappush() n times is O(n log n). For large inputs the difference is measurable. Know which one you're using and why.
Assuming heap order means sorted order. heap[1] is NOT necessarily the second-smallest element. The second-smallest is either heap[1] or heap[2], and you'd need to compare them. If you need the k-th element, pop k times or use a different structure.
Custom comparators in Java and C++. Python's negation trick works for numbers. For objects in Java, pass a lambda to the PriorityQueue constructor. In C++, use a comparator struct or lambda. Fumbling this syntax in an interview is a time sink you can't afford. Know your language cold before walking in.
The Short Version
- Min-heap: complete binary tree, parent ≤ both children
- Stored as a plain array; all parent-child relationships are O(1) index math
- Insert sifts up, extract-min sifts down; both are O(log n)
- Heapify from an unsorted array is O(n), not O(n log n)
- Python's
heapqis min-only; negate values to simulate max-heap - Top-K smallest uses a max-heap of size K, not a min-heap of everything
- The heap is not sorted; arbitrary lookup is O(n)
For a full implementation in 14 languages with edge case analysis, see the heap data structure reference. If you want to work through the most common heap interview problems, heap interview problems has a curated set with pattern breakdowns. The top-K heap pattern goes deeper on the max-heap-of-size-K insight, the most frequently misapplied technique in this category.