What is a Min-Heap?
Learn what a min-heap is, how sift-up and sift-down work, and how to answer this data structures interview question.
Expected Interview Answer
A min-heap is a complete binary tree, usually stored as an array, where every parent node is less than or equal to its children, guaranteeing the smallest element always sits at the root and giving O(1) peek plus O(log n) insert and remove-min.
Because the tree is complete, it can be packed into a plain array with no pointers, where the children of index i sit at 2i+1 and 2i+2 and the parent of index i sits at (i-1)//2. Inserting appends a new value at the end of the array then sifts it upward, swapping with its parent while it is smaller, until the heap property holds. Removing the minimum swaps the root with the last element, shrinks the array, then sifts the new root downward against its smaller child until order is restored. A min-heap only guarantees the root is the smallest — siblings and deeper levels are not fully sorted relative to each other, which is why it powers priority queues, Dijkstra's algorithm, and the k-smallest-elements pattern rather than being used as a sorted structure directly.
- O(1) peek at the current minimum
- O(log n) insert and extract-min
- Compact array storage, no pointer overhead
- Core of priority queues and Dijkstra’s shortest path
AI Mentor Explanation
A fielding captain keeps the fittest, freshest bowler always ready at the front of a rotation tree without ranking the entire squad. A newly rested bowler is slotted at the back and swapped forward only past more tired bowlers, stopping as soon as the bowler ahead is fresher still. When the freshest bowler finishes an over, the last bowler in the rotation takes the front slot and is pushed back against fresher children until order holds again. This partial reordering, not a full squad ranking, is why the next-freshest bowler is always known instantly, exactly how a min-heap keeps its minimum at the root.
Step-by-Step Explanation
Step 1
Store as a complete array
Element at index i has children at 2i+1 and 2i+2, and parent at (i-1)//2.
Step 2
Insert: append and sift up
Add the new value at the end, then swap with its parent while the parent is larger.
Step 3
Remove-min: swap root with last, sift down
Move the last element to the root, then swap with the smaller child repeatedly until order holds.
Step 4
Use for priority access
Peek at the minimum is O(1); insert and extract-min are O(log n) — ideal for priority queues and Dijkstra.
What Interviewer Expects
- State the heap property: every parent ≤ its children
- Explain array indexing (2i+1, 2i+2, parent at (i-1)//2) without pointers
- Walk through sift-up on insert and sift-down on extract-min
- Name real uses: priority queues, Dijkstra’s algorithm, k-smallest-elements problems
Common Mistakes
- Assuming a min-heap is fully sorted left to right (it is only partially ordered)
- Confusing a min-heap with a binary search tree
- Forgetting extract-min takes O(log n), not O(1)
- Mixing up the parent and child index formulas
Best Answer (HR Friendly)
“A min-heap is a tree-shaped structure stored in an array that always keeps the smallest value at the top, so I can grab it instantly. I use it whenever I need to repeatedly pull out the current smallest item efficiently, like in a priority queue or Dijkstra's shortest path algorithm.”
Code Example
import heapq
min_heap = []
heapq.heappush(min_heap, 8)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 5)
smallest = heapq.heappop(min_heap) # 3, O(log n)
peek = min_heap[0] # O(1), current minimum
def k_smallest(nums, k):
return heapq.nsmallest(k, nums) # uses a min-heap internallyFollow-up Questions
- How would you build a min-heap from an unsorted array in O(n)?
- How do you find the k smallest elements in a stream using a min-heap?
- How is a min-heap different from a binary search tree?
- How would you implement a max-heap using Python’s min-heap-only heapq?
MCQ Practice
1. What value sits at the root of a min-heap?
The min-heap property guarantees every parent is ≤ its children, so the smallest value is always at the root.
2. What is the time complexity of extracting the minimum from a min-heap of n elements?
Extraction swaps in the last element then sifts it down, which takes O(log n).
3. In an array-based min-heap, what is the index of the parent of node i?
The parent of index i is stored at (i - 1) // 2 in a zero-indexed array heap.
Flash Cards
What property defines a min-heap? — Every parent node is less than or equal to its children.
What is the time complexity of min-heap insert? — O(log n), due to the sift-up operation.
How are min-heap children indexed in an array? — Children of index i are at 2i+1 and 2i+2.
Name a classic use of a min-heap. — Priority queues and Dijkstra’s shortest path algorithm (also k-smallest-elements problems).