Autocoder

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 operationspush and pop O(log n), peek O(1), heapify O(n)
Pythonheapq is a min-heap only
JavaPriorityQueue is a min-heap by default
Signal wordstop 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

Heap and Priority Queue Interview Questions: questions with worked answers

  1. 1

    Last stone weight

    easy

    Repeatedly 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.

    python
    import 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 0
    java
    int 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. 2

    Kth largest element in a stream

    easy

    Keep 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.

    python
    import 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]
    java
    class 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. 3

    Top K frequent elements

    medium

    Count 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.

    python
    import 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]
    java
    int[] 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. 4

    K closest points to the origin

    medium

    Squared 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).

    python
    import 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]
    java
    int[][] 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. 5

    Merge k sorted lists

    medium

    Push 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.

    python
    import 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.next
    java
    ListNode 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. 6

    Minimum cost to connect ropes

    medium

    Always 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).

    python
    import 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 cost
    java
    long 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. 7

    Sort an array where each element is at most k places from its sorted position

    medium

    The 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.

    python
    import 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 out
    java
    int[] 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. 8

    Reorganise a string so no two adjacent characters match

    medium

    Greedy: 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.

    python
    import 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 ''
    java
    String 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. 9

    Median of a data stream

    hard

    Split 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).

    python
    import 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]) / 2
    java
    class 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. 10

    Find K pairs with the smallest sums from two sorted arrays

    hard

    The 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.

    python
    import 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 res
    java
    List<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. 11

    Minimum number of meeting rooms

    hard

    Sort 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.

    python
    import 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)
    java
    int 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

See all in this section