Heap basics
In one line
A heap is a complete binary tree stored in an array where every parent is no larger (min-heap) or no smaller (max-heap) than its children, so the smallest or largest item is always at the top: peek in O(1), push and pop in O(log n).
What it is
A binary heap is a binary tree with two rules. Shape rule: it is complete, meaning every level is full except possibly the last, which fills from left to right. Order rule: in a min-heap every parent is less than or equal to its children (in a max-heap, greater than or equal). The order rule only links parents and children, so siblings are in no particular order and the array is not sorted.
Because the tree is complete, it fits in a plain array with no pointers. For the item at index i, the children are at 2i + 1 and 2i + 2 and the parent is at (i - 1) // 2. The minimum (or maximum) is always at index 0.
A priority queue is the abstract idea: 'give me the item with the highest priority next'. A heap is the usual way to build one. Python's heapq module and Java's PriorityQueue are both binary min-heaps.
Why interviewers ask
Heaps show up whenever a problem says 'k-th', 'top k', 'smallest so far', 'merge sorted' or 'next event'. Interviewers test whether you know the exact costs (O(1) peek, O(log n) push and pop, O(n) heapify, O(n) search), whether you can explain sift up and sift down, and whether you reach for a heap instead of re-sorting the data after every change.
How it works
- 1Peek: the minimum is a[0]. O(1).
- 2Push: append the new item at the end of the array (the next free spot in the last level), then sift up: while it is smaller than its parent, swap them. The tree has height about log2 n, so this is O(log n).
- 3Pop: save a[0], move the last item into the root, shrink the array, then sift down: swap the item with its smaller child while that child is smaller. O(log n).
- 4Heapify: to build a heap from n unsorted items, sift down every non-leaf node starting from the last one, (n // 2) - 1, back to 0. This is O(n) total, not O(n log n), because most nodes are near the bottom and move only a little.
- 5Max-heap in Python: heapq only has a min-heap, so push -x and negate again on pop, or push tuples like (-priority, item).
- 6Heap sort: heapify, then pop n times. O(n log n) time, O(1) extra space if done in place, but not stable.
Worked example · Push 5, 3, 8, 1 into a min-heap, then pop once
- push 5: array [5].
- push 3: append -> [5, 3]. Index 1's parent is index 0 (5). 3 < 5, swap -> [3, 5].
- push 8: append -> [3, 5, 8]. Parent of index 2 is index 0 (3). 8 > 3, stop.
- push 1: append -> [3, 5, 8, 1]. Parent of index 3 is index 1 (5): swap -> [3, 1, 8, 5]. Parent of index 1 is index 0 (3): swap -> [1, 3, 8, 5]. The minimum 1 is at the top.
- pop: save 1. Move the last item 5 to the root -> [5, 3, 8]. Children of index 0 are 3 and 8; the smaller is 3 < 5, swap -> [3, 5, 8]. Index 1 has no children, stop. Return 1.
- Notice [1, 3, 8, 5] was a valid heap even though it is not sorted: only parent-child order matters.
Picture it
A heap is like a hospital emergency room queue. Nobody keeps the whole waiting list perfectly sorted; staff only make sure the most urgent patient is always next. When a new patient arrives or one is called in, a few quick comparisons restore that guarantee.
Reference code
class MinHeap:
def __init__(self):
self.a = []
def push(self, x): # O(log n)
a = self.a
a.append(x)
i = len(a) - 1
while i > 0 and a[(i - 1) // 2] > a[i]: # sift up
p = (i - 1) // 2
a[i], a[p] = a[p], a[i]
i = p
def pop(self): # O(log n), removes the minimum
a = self.a
top, last = a[0], a.pop()
if a:
a[0] = last
i, n = 0, len(a)
while True: # sift down
small, l, r = i, 2 * i + 1, 2 * i + 2
if l < n and a[l] < a[small]:
small = l
if r < n and a[r] < a[small]:
small = r
if small == i:
break
a[i], a[small] = a[small], a[i]
i = small
return topThe heap is a list where the children of i are 2i + 1 and 2i + 2. push appends and sifts up while the parent is larger; pop moves the last item to the root and sifts down toward the smaller child. In practice you would use heapq.heappush, heapq.heappop and heapq.heapify, which do exactly this.
Key patterns
Min-heap or max-heap by negation
When: You need the largest item but your library only has a min-heap
How: Push -x (or (-priority, item)) and negate on pop.
Tuple keys with tie-breakers
When: Items are objects that cannot be compared
How: Push (priority, counter, item) so equal priorities compare the unique counter instead of the item.
Heapify in O(n)
When: You have all items up front
How: Call heapq.heapify(list) instead of n pushes (O(n log n)).
Lazy deletion
When: You must remove or update arbitrary items
How: Mark items as stale in a hash map, push the new version, and skip stale items when they reach the top.
Real-world use
Language standard libraries
Python's heapq, Java's PriorityQueue and C++'s std::priority_queue are binary heaps over arrays; they are the default tool for priority queues in application code.
Shortest-path routing
Dijkstra's algorithm pops the closest unvisited node from a priority queue. Link-state routing protocols such as OSPF run Dijkstra's shortest path first on every router to build routing tables.
Timers and scheduled callbacks
Python's asyncio event loop keeps call_later callbacks in a heapq ordered by due time, and Java's ScheduledThreadPoolExecutor uses a heap-based delayed work queue, so the next timer to fire is always at the top.
Database top-N sorting
PostgreSQL uses a bounded 'top-N heapsort' for ORDER BY ... LIMIT N when N is small, keeping only N rows in memory instead of sorting the whole result.
In a project
You are building a job queue for a backend where paid customers' jobs must run before free customers' jobs, and among equal priorities older jobs run first.
- Store pending jobs in a min-heap keyed by (priority, enqueue_time, job_id), where paid = 0 and free = 1; the job_id breaks ties so jobs themselves never need to be compared.
- Workers pop the top of the heap to get the next job in O(log n).
- To avoid starving free users, periodically lower the priority number of jobs that have waited longer than a threshold (aging), by re-inserting them.
- Expose the heap size and the age of the top job as metrics.
Impact: Each enqueue and dequeue stays O(log n) even with 100,000 pending jobs, instead of re-sorting the list on every change, and paid jobs consistently start within seconds while free jobs still finish thanks to aging.
Trade-offs
Use it when
- You repeatedly need the current smallest or largest item while items keep arriving
- You need only the top few items, not a fully sorted list
- You process events in time or priority order (timers, simulations, Dijkstra)
Avoid it when
- You need to search for or delete arbitrary items often: that is O(n) in a heap; use a balanced BST or sorted container
- You need the data in full sorted order once: just sort
- You need both the minimum and the maximum: use two heaps or a sorted structure
Cost: Peek O(1). Push and pop O(log n). Heapify O(n). Search or arbitrary delete O(n). Heap sort O(n log n), not stable. Space O(n).
Common mistakes
- Thinking the heap array is sorted; only parent-child order holds (the second smallest is at a[1] or a[2], but you do not know which).
- Saying building a heap from n items is O(n log n); heapify is O(n).
- Claiming you can find an arbitrary item in O(log n); search is O(n).
- Forgetting that Python's heapq is a min-heap and getting the smallest instead of the largest.
- Pushing objects without a tie-breaker, so equal priorities make Python compare the objects and raise a TypeError.
Interview questions
Quick revision
- Heap = complete binary tree + parent <= children (min-heap).
- Array layout: children 2i + 1, 2i + 2; parent (i - 1) // 2; top at a[0].
- Peek O(1); push and pop O(log n); heapify O(n); search O(n).
- Push = append + sift up; pop = last to root + sift down.
- Python heapq is a min-heap; negate for a max-heap.
- Use (priority, counter, item) tuples to break ties safely.
- Heap sort: O(n log n), in place, not stable.
Check yourself
1. In a min-heap stored as an array, where are the children of index 3?
2. What is the time complexity of building a heap from n unsorted items with heapify?
3. Which array is a valid min-heap?
4. Which operation is O(n) in a binary heap?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.