What is a Heap?
Learn what a heap data structure is, how min-heap and max-heap work, and how to answer this common data structures interview question.
Expected Interview Answer
A heap is a complete binary tree stored in an array that satisfies the heap property — in a min-heap every parent is smaller than or equal to its children, giving O(1) access to the minimum and O(log n) insert and remove.
Because the tree is complete, it can be stored compactly in an array with no pointers: the children of index i live at 2i+1 and 2i+2. Inserting appends a new element then “sifts up” to restore order; removing the root swaps in the last element then “sifts down”. Heaps power priority queues, heapsort, and algorithms like Dijkstra and A* that repeatedly need the current best candidate. A max-heap flips the property so the largest element sits at the root.
- O(1) peek at min or max
- O(log n) insert and extract
- Array-based, no pointer overhead
- Backbone of priority queues
AI Mentor Explanation
A knockout net-practice queue keeps the fastest bowler always ready to bowl next: coaches insert new bowlers at the back and let them work their way forward only until they beat someone slower, not all the way to the front. When the star bowler finishes an over, the last bowler in line steps up and gets compared down against the remaining bowlers until order is restored. Nobody sorts the whole queue; only the promoted bowler moves, which is why the next-best bowler is always available in O(log n) shuffles.
Step-by-Step Explanation
Step 1
Store as a complete array
Element at index i has children at 2i+1 and 2i+2, parent at (i-1)//2.
Step 2
Insert: append and sift up
Add at the end, then swap with parent while it violates the heap property.
Step 3
Remove: swap root with last, sift down
Move the last element to the root, then swap with the smaller (or larger) child repeatedly.
Step 4
Use for priority access
Peek is O(1); insert and extract-min/max are O(log n) — ideal for priority queues.
What Interviewer Expects
- Distinguish min-heap vs max-heap
- Explain array indexing (2i+1, 2i+2) without pointers
- Walk through sift-up on insert and sift-down on removal
- Name real uses: priority queues, heapsort, Dijkstra, top-K problems
Common Mistakes
- Assuming a heap is fully sorted (it is only partially ordered)
- Confusing a heap with a binary search tree
- Forgetting removal takes O(log n), not O(1)
- Mixing up parent/child index formulas
Best Answer (HR Friendly)
“A heap is a data structure shaped like a tree but stored in an array, and it always keeps the smallest — or largest — item easy to grab. I use it whenever I need to repeatedly pull out the “next most important” item quickly, like a task scheduler or a priority queue.”
Code Example
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
smallest = heapq.heappop(heap) # 1, O(log n)
peek = heap[0] # O(1), current minimum
def top_k_smallest(nums, k):
return heapq.nsmallest(k, nums) # uses a heap internallyFollow-up Questions
- How would you find the k largest elements in a stream?
- How does heapsort use a heap to sort in place?
- How is a heap different from a balanced binary search tree?
- How would you implement a max-heap using Python’s min-heap-only heapq?
MCQ Practice
1. 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).
2. In an array-based heap, what is the index of the left child of node i?
The left child of index i is stored at 2i + 1 in a zero-indexed array heap.
3. Which statement about heaps is true?
The heap property guarantees the root is always the min (or max), giving O(1) peek.
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 heap insert? — O(log n), due to the sift-up operation.
How are heap children indexed in an array? — Children of index i are at 2i+1 and 2i+2.
Name two classic uses of a heap. — Priority queues and heapsort (also Dijkstra’s algorithm and top-K problems).