Heap and Priority Queue Interview Questions
Last updated 2026-11-19
A heap gives you the smallest or largest item in O(1) and removes it in O(log n). Whenever a problem asks for the top K, the K-th best, a running median or repeatedly processing the most urgent item, a heap is the first structure to consider.
These problems run from easy to hard and each shows the approach, Python (heapq, a min-heap) and Java (PriorityQueue) code, complexity and edge cases. For sorting-based alternatives see arrays interview questions.
| Core operations | push and pop O(log n), peek O(1), heapify O(n) |
|---|---|
| Python | heapq is a min-heap only |
| Java | PriorityQueue is a min-heap by default |
| Signal words | top K, K-th, median, merge, schedule |
The pattern and when to spot it
The size-k trick is the most reusable idea. To find the k largest values, keep a min-heap of size k: the root is the smallest of the winners and is the one to evict when something better arrives. This costs O(n log k) instead of O(n log n) sorting and works on streams. For k smallest, flip it and use a max-heap.
Two-heap problems, such as the running median, split data into a lower half in a max-heap and an upper half in a min-heap. Scheduling problems, such as meeting rooms and ropes, sort first and use a heap for the earliest finishing resource. Graph shortest path problems also rely on heaps, see Dijkstra interview questions.
Language details that cause bugs
- Python has no max-heap, so negate values or store negative counts.
- Python compares tuples element by element, so add an index as a tiebreaker when the second item is not comparable, such as a list node.
- Java comparators that subtract integers can overflow. Use Integer.compare or Long.compare for large values.
- PriorityQueue iteration order is not sorted. Only poll gives order.
- Building a heap from a list with heapify is O(n), cheaper than n pushes.
Heap and Priority Queue Interview Questions: questions with worked answers
1 Last stone weight
easyRepeatedly smash the two heaviest stones. A max-heap gives the heaviest two in O(log n). Python has only a min-heap, so push negated values. Push back the difference if it is non-zero. Time O(n log n), space O(n). Edge cases: one stone, all stones equal (they cancel to zero), empty result returns 0.
pythonimport heapq def last_stone(stones): h = [-s for s in stones] heapq.heapify(h) while len(h) > 1: a, b = -heapq.heappop(h), -heapq.heappop(h) if a != b: heapq.heappush(h, -(a - b)) return -h[0] if h else 0javaint lastStone(int[] stones) { PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); for (int s : stones) pq.add(s); while (pq.size() > 1) { int a = pq.poll(), b = pq.poll(); if (a != b) pq.add(a - b); } return pq.isEmpty() ? 0 : pq.peek(); }2 Kth largest element in a stream
easyKeep a min-heap of size k that holds the k largest values seen. Its root is the kth largest. On each add, push the value and pop if the size exceeds k. Time O(log k) per add, space O(k). Edge cases: fewer than k elements initially, duplicate values, negative numbers.
pythonimport heapq class KthLargest: def __init__(self, k, nums): self.k, self.h = k, [] for x in nums: self.add(x) def add(self, val): heapq.heappush(self.h, val) if len(self.h) > self.k: heapq.heappop(self.h) return self.h[0]javaclass KthLargest { private final PriorityQueue<Integer> pq = new PriorityQueue<>(); private final int k; KthLargest(int k, int[] nums) { this.k = k; for (int x : nums) add(x); } int add(int val) { pq.add(val); if (pq.size() > k) pq.poll(); return pq.peek(); } }3 Top K frequent elements
mediumCount frequencies with a hash map, then keep a min-heap of size k ordered by count. Pop the smallest whenever the heap grows past k. Bucket sort by frequency gives O(n) as an alternative. Time O(n log k), space O(n). Edge cases: k equal to the number of distinct values, ties (any order is usually accepted), single element.
pythonimport heapq from collections import Counter def top_k_frequent(nums, k): cnt = Counter(nums) h = [] for v, c in cnt.items(): heapq.heappush(h, (c, v)) if len(h) > k: heapq.heappop(h) return [v for c, v in h]javaint[] topK(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) cnt.merge(x, 1, Integer::sum); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); for (var e : cnt.entrySet()) { pq.add(new int[]{e.getKey(), e.getValue()}); if (pq.size() > k) pq.poll(); } int[] res = new int[k]; for (int i = 0; i < k; i++) res[i] = pq.poll()[0]; return res; }4 K closest points to the origin
mediumSquared distance preserves ordering, so skip the square root. Keep a max-heap of size k keyed by distance, evicting the farthest. Quickselect gives O(n) average if the heap is not required. Time O(n log k), space O(k). Edge cases: k equal to n, two points at the same distance, points at the origin, large coordinates where squared distance overflows int (use long).
pythonimport heapq def k_closest(points, k): h = [] for x, y in points: heapq.heappush(h, (-(x * x + y * y), x, y)) if len(h) > k: heapq.heappop(h) return [[x, y] for _, x, y in h]javaint[][] kClosest(int[][] points, int k) { PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> Long.compare(dist(b), dist(a))); for (int[] p : points) { pq.add(p); if (pq.size() > k) pq.poll(); } return pq.toArray(new int[0][]); } private long dist(int[] p) { return (long) p[0] * p[0] + (long) p[1] * p[1]; }5 Merge k sorted lists
mediumPush the head of each list into a min-heap keyed by value. Pop the smallest, append it to the result and push that node successor. The heap never holds more than k nodes. A tie-breaking index avoids comparing nodes in Python. Time O(N log k) for N total nodes, space O(k). Edge cases: empty lists in the input, all lists empty, duplicates across lists, k equal to 1.
pythonimport heapq def merge_k(lists): h = [(l.val, i, l) for i, l in enumerate(lists) if l] heapq.heapify(h) dummy = tail = ListNode(0) while h: _, i, node = heapq.heappop(h) tail.next = node tail = node if node.next: heapq.heappush(h, (node.next.val, i, node.next)) return dummy.nextjavaListNode mergeK(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val); for (ListNode l : lists) if (l != null) pq.add(l); ListNode dummy = new ListNode(0), tail = dummy; while (!pq.isEmpty()) { ListNode n = pq.poll(); tail.next = n; tail = n; if (n.next != null) pq.add(n.next); } return dummy.next; }6 Minimum cost to connect ropes
mediumAlways join the two shortest ropes, as in Huffman coding, because each early join cost is paid again by every later join that includes it. Use a min-heap and add each combined length to the total. Time O(n log n), space O(n). Edge cases: a single rope costs 0, two ropes, equal lengths, totals exceeding int range (use long).
pythonimport heapq def connect_ropes(ropes): heapq.heapify(ropes) cost = 0 while len(ropes) > 1: s = heapq.heappop(ropes) + heapq.heappop(ropes) cost += s heapq.heappush(ropes, s) return costjavalong connectRopes(int[] ropes) { PriorityQueue<Long> pq = new PriorityQueue<>(); for (int r : ropes) pq.add((long) r); long cost = 0; while (pq.size() > 1) { long s = pq.poll() + pq.poll(); cost += s; pq.add(s); } return cost; }7 Sort an array where each element is at most k places from its sorted position
mediumThe correct element for position i is among the next k+1 items. Keep a min-heap of size k+1, pop the smallest into the output and slide the window. This beats full sorting when k is small. Time O(n log k), space O(k). Edge cases: k equal to 0 (already sorted), k at least n (reduces to heap sort), duplicates.
pythonimport heapq def sort_k_sorted(a, k): h = a[:k + 1] heapq.heapify(h) out = [] for x in a[k + 1:]: out.append(heapq.heappushpop(h, x)) while h: out.append(heapq.heappop(h)) return outjavaint[] sortKSorted(int[] a, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(); int[] out = new int[a.length]; int idx = 0; for (int i = 0; i < a.length; i++) { pq.add(a[i]); if (pq.size() > k) out[idx++] = pq.poll(); } while (!pq.isEmpty()) out[idx++] = pq.poll(); return out; }8 Reorganise a string so no two adjacent characters match
mediumGreedy: always place the most frequent remaining character that differs from the last one placed. Use a max-heap of counts, hold the previous character out for one round, then return it to the heap. If the heap empties while a held character still has count left, it is impossible. Time O(n log 26), effectively O(n), space O(26). Edge cases: one character with more than (n+1)/2 occurrences, single character string, all distinct characters.
pythonimport heapq from collections import Counter def reorganize(s): h = [(-c, ch) for ch, c in Counter(s).items()] heapq.heapify(h) out, prev = [], None while h: c, ch = heapq.heappop(h) out.append(ch) if prev: heapq.heappush(h, prev) prev = None if c + 1 < 0: prev = (c + 1, ch) return ''.join(out) if not prev else ''javaString reorganize(String s) { int[] cnt = new int[26]; for (char c : s.toCharArray()) cnt[c - 'a']++; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]); for (int i = 0; i < 26; i++) if (cnt[i] > 0) pq.add(new int[]{i, cnt[i]}); StringBuilder sb = new StringBuilder(); int[] prev = null; while (!pq.isEmpty()) { int[] cur = pq.poll(); sb.append((char) ('a' + cur[0])); cur[1]--; if (prev != null) { pq.add(prev); prev = null; } if (cur[1] > 0) prev = cur; } return prev == null ? sb.toString() : ""; }9 Median of a data stream
hardSplit the numbers into a max-heap for the smaller half and a min-heap for the larger half, and keep their sizes equal or with the lower heap one bigger. The median is the lower root or the mean of both roots. On each insert, push to the lower heap, move its top to the upper heap, then rebalance. Time O(log n) per add, O(1) median, space O(n). Edge cases: empty stream, odd and even counts, repeated values, very large sums (use double or long).
pythonimport heapq class MedianFinder: def __init__(self): self.lo, self.hi = [], [] # lo is a max-heap via negation def add(self, x): heapq.heappush(self.lo, -x) heapq.heappush(self.hi, -heapq.heappop(self.lo)) if len(self.hi) > len(self.lo): heapq.heappush(self.lo, -heapq.heappop(self.hi)) def median(self): if len(self.lo) > len(self.hi): return float(-self.lo[0]) return (-self.lo[0] + self.hi[0]) / 2javaclass MedianFinder { private final PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); private final PriorityQueue<Integer> hi = new PriorityQueue<>(); void add(int x) { lo.add(x); hi.add(lo.poll()); if (hi.size() > lo.size()) lo.add(hi.poll()); } double median() { if (lo.size() > hi.size()) return lo.peek(); return ((double) lo.peek() + hi.peek()) / 2.0; } }10 Find K pairs with the smallest sums from two sorted arrays
hardThe smallest pair is (0,0). Start a min-heap with (a[i] + b[0], i, 0) for the first min(k, len(a)) values of i. Each pop produces a result pair and pushes the next candidate (i, j+1). This explores only O(k) pairs instead of all n*m. Time O(k log k), space O(k). Edge cases: either array empty, k larger than n*m (return all pairs), duplicate values, large sums needing long.
pythonimport heapq def k_smallest_pairs(a, b, k): if not a or not b: return [] h = [(a[i] + b[0], i, 0) for i in range(min(k, len(a)))] heapq.heapify(h) res = [] while h and len(res) < k: _, i, j = heapq.heappop(h) res.append([a[i], b[j]]) if j + 1 < len(b): heapq.heappush(h, (a[i] + b[j + 1], i, j + 1)) return resjavaList<List<Integer>> kSmallestPairs(int[] a, int[] b, int k) { List<List<Integer>> res = new ArrayList<>(); if (a.length == 0 || b.length == 0) return res; PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Long.compare((long) x[0], (long) y[0])); for (int i = 0; i < Math.min(k, a.length); i++) pq.add(new int[]{a[i] + b[0], i, 0}); while (!pq.isEmpty() && res.size() < k) { int[] t = pq.poll(); res.add(Arrays.asList(a[t[1]], b[t[2]])); if (t[2] + 1 < b.length) pq.add(new int[]{a[t[1]] + b[t[2] + 1], t[1], t[2] + 1}); } return res; }11 Minimum number of meeting rooms
hardSort meetings by start time. Keep a min-heap of end times of rooms in use. If the earliest ending meeting finishes at or before the new start, reuse that room by popping it. Push the new end. The heap size at the end is the room count. Time O(n log n), space O(n). Edge cases: back-to-back meetings (end equals start reuses the room), identical intervals, empty input returns 0.
pythonimport heapq def min_rooms(intervals): h = [] for s, e in sorted(intervals): if h and h[0] <= s: heapq.heappop(h) heapq.heappush(h, e) return len(h)javaint minRooms(int[][] iv) { Arrays.sort(iv, (a, b) -> a[0] - b[0]); PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int[] m : iv) { if (!pq.isEmpty() && pq.peek() <= m[0]) pq.poll(); pq.add(m[1]); } return pq.size(); }
Frequently asked questions
What is the difference between a heap and a priority queue?
A priority queue is the abstract idea of removing the highest-priority item first. A binary heap is the usual array-based structure that implements it with O(log n) push and pop.
Why is building a heap O(n) and not O(n log n)?
Most nodes sit near the bottom and sift down very little. Summing the work over all levels converges to a linear total, which is why heapify beats n repeated pushes.
When should I use a heap instead of sorting?
Use a heap when you need only the top K, when data arrives as a stream, or when the best item changes as you process. Sorting is simpler if you need everything ordered once.
How do I get a max-heap in Python or Java?
In Python push negated values. In Java pass Collections.reverseOrder() or a comparator such as (a, b) -> Integer.compare(b, a) to PriorityQueue.
Related guides
More in DSA Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions