Heap & Priority Queue Interview Problems: Top-K, Merge K Lists & Median of a Stream

Heaps are the quiet workhorse of coding interviews. They rarely appear as "implement a heap", but they sit underneath Kth largest element, merge K sorted lists, find median from data stream, meeting rooms, task scheduler, Dijkstra and a dozen "design a leaderboard" questions. If you can spot that a problem wants "the current best element, over and over", you already have half the solution.

This guide starts with how the structure works internally (interviewers do ask why heapify is linear), then walks through the five patterns with code in Java, C++ and Python, dry runs, complexity, and the follow-up questions you should expect.

How a Binary Heap Works Under the Hood

A binary min-heap is a complete binary tree in which every parent is less than or equal to its children. "Complete" means every level is full except possibly the last, which is filled left to right. That shape constraint is what lets us store the tree in a plain array with no pointers.

For a 0-indexed array, the node at index i has:

• left child at 2i + 1
• right child at 2i + 2
• parent at (i - 1) / 2 (integer division)

Note what the heap does not guarantee: the array is not sorted, and siblings have no order between them. Only the root is special. That weaker invariant is why heap operations are cheaper than keeping a sorted structure.

Push: append and sift up

Append the new value at the end of the array (keeps the tree complete), then swap it with its parent while it is smaller than the parent. The tree height is floor(log2 n), so push is O(log n).

Pop: move the last element to the root and sift down

Save the root, move the last element into index 0, shrink the array, then repeatedly swap the element with its smaller child until neither child is smaller. Again O(log n). Swapping with the smaller child is essential: swapping with the larger one would put a bigger value above a smaller sibling and break the invariant.

Heapify: why building a heap is O(n)

Given an unsorted array, call sift-down on every internal node from index n/2 - 1 down to 0. A node at height h costs O(h) to sift down, and there are at most n / 2^(h+1) nodes at height h. The total work is sum over h of n·h / 2^(h+1), and since sum h/2^h = 2, this is bounded by O(n). Half the nodes are leaves that cost nothing, a quarter cost one swap, and so on.

That is a classic follow-up: "If I give you all n elements up front, can you do better than n pushes?" Yes: heapq.heapify(list) in Python, the PriorityQueue(Collection) constructor in Java, and std::make_heap or the range constructor of priority_queue in C++ all run in linear time.

class MinHeap:
    def __init__(self):
        self.a = []

    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0:
            p = (i - 1) // 2
            if a[p] <= a[i]:
                break
            a[p], a[i] = a[i], a[p]
            i = p

    def pop(self):
        a = self.a
        top = a[0]
        last = a.pop()
        if a:
            a[0] = last
            self._sift_down(0)
        return top

    def _sift_down(self, i):
        a, n = self.a, len(self.a)
        while True:
            l, r, smallest = 2 * i + 1, 2 * i + 2, i
            if l < n and a[l] < a[smallest]:
                smallest = l
            if r < n and a[r] < a[smallest]:
                smallest = r
            if smallest == i:
                return
            a[i], a[smallest] = a[smallest], a[i]
            i = smallest

    def peek(self):
        return self.a[0]

    def __len__(self):
        return len(self.a)

You will almost never be asked to write this in a product-company round, but writing it once removes the mystery, and some service-company and campus rounds (and the occasional Amazon phone screen) do ask it directly.

Priority Queue APIs in Java, C++ and Python

Half of the time lost in heap questions is fighting the language. Memorise this table.

For custom objects: Python compares tuples element by element, so push (priority, counter, obj) with a unique counter to break ties. Java takes a Comparator. C++ takes a comparator type where cmp(a, b) == true means a has lower priority (it goes further from the top), which is why greater<int> produces a min-heap. If you write C++, the C++ STL guide for coding interviews covers this inversion in detail; Java users should see the Java Collections guide.

When to Reach for a Heap: Recognition Signals

Ask yourself whether the problem needs the extreme element repeatedly while the set of candidates changes. If you need the minimum once, a linear scan is fine. If the set never changes, sort it. A heap wins when both are true.

Pattern 1: Top-K Elements with a Size-K Heap

The counter-intuitive rule: to keep the K largest, use a min-heap. The heap holds the best K seen so far, and its root is the weakest member of that elite group, the one to evict when something better arrives.

Kth Largest Element in an Array (LeetCode 215)

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int x : nums) {
        minHeap.offer(x);
        if (minHeap.size() > k) {
            minHeap.poll();          // evict the smallest of k+1
        }
    }
    return minHeap.peek();           // smallest of the k largest
}

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int x : nums) {
        minHeap.push(x);
        if ((int)minHeap.size() > k) minHeap.pop();
    }
    return minHeap.top();
}

import heapq

def find_kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)                  # O(k)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)   # pop root, push x in one sift
    return heap[0]

Dry run with nums = [3, 2, 1, 5, 6, 4], k = 2 (Python version): initial heap [2, 3]. See 1: not bigger than 2, skip. See 5: replace 2, heap [3, 5]. See 6: replace 3, heap [5, 6]. See 4: not bigger than 5, skip. Answer: root = 5. Correct, the sorted array is [1,2,3,4,5,6] and the 2nd largest is 5.

Complexity: O(n log k) time, O(k) space. When interviewers push for better, mention quickselect: O(n) average, O(n²) worst case, in-place, but unusable on a stream. The full trade-off discussion is in LeetCode 215 explained.

Top K Frequent Elements (LeetCode 347)

Count frequencies with a hash map, then run the same size-K min-heap keyed on frequency.

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);

    PriorityQueue<int[]> heap =
        new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        heap.offer(new int[]{e.getKey(), e.getValue()});
        if (heap.size() > k) heap.poll();
    }
    int[] res = new int[k];
    for (int i = k - 1; i >= 0; i--) res[i] = heap.poll()[0];
    return res;
}

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    freq = Counter(nums)
    return heapq.nlargest(k, freq.keys(), key=freq.get)

Time O(n + m log k) where m is the number of distinct values. The famous follow-up is "can you do it in O(n)?" Answer: bucket sort by frequency. Frequencies range from 1 to n, so create n+1 buckets, put each value in bucket[freq], and walk from the top bucket down until you have K values.

K Closest Points to Origin (LeetCode 973)

Same pattern, but "closest" means we keep the K smallest distances, so we need a max-heap of size K whose root is the farthest of the current K. Compare squared distances to avoid floating point: x*x + y*y. With coordinates up to 10⁴, squared distance fits comfortably in a 32-bit int (at most 2×10⁸).

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    // max-heap of (distance, index)
    priority_queue<pair<int, int>> heap;
    for (int i = 0; i < (int)points.size(); i++) {
        int d = points[i][0] * points[i][0] + points[i][1] * points[i][1];
        heap.push({d, i});
        if ((int)heap.size() > k) heap.pop();
    }
    vector<vector<int>> res;
    while (!heap.empty()) {
        res.push_back(points[heap.top().second]);
        heap.pop();
    }
    return res;
}

Pattern 2: K-Way Merge (Merge K Sorted Lists and Friends)

When you have K sorted sequences, the next smallest element overall must be the head of one of them. Put all K heads in a min-heap; pop the smallest, output it, push its successor from the same list. The heap never holds more than K items.

Merge K Sorted Lists (LeetCode 23)

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap =
        new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
    for (ListNode head : lists) {
        if (head != null) heap.offer(head);
    }
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        tail.next = node;
        tail = node;
        if (node.next != null) heap.offer(node.next);
    }
    return dummy.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
    for (ListNode* head : lists)
        if (head) heap.push(head);
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!heap.empty()) {
        ListNode* node = heap.top();
        heap.pop();
        tail->next = node;
        tail = node;
        if (node->next) heap.push(node->next);
    }
    return dummy.next;
}

import heapq

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heap.append((node.val, i, node))   # i breaks ties: ListNode is not comparable
    heapq.heapify(heap)
    dummy = tail = ListNode(0)
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Dry run with lists A = 1→4→5, B = 1→3→4, C = 2→6:

Complexity: N total nodes, each pushed and popped once on a heap of size at most K: O(N log K) time, O(K) extra space. Interviewers frequently ask for the alternative: divide and conquer pairwise merging (merge lists 0+1, 2+3, ... then repeat) is also O(N log K) with O(1) extra space if done iteratively. The naive "merge one list at a time into the result" is O(N·K), and that is the answer they are trying to steer you away from.

Kth Smallest Element in a Sorted Matrix (LeetCode 378)

Each row is a sorted list, so this is K-way merge where you stop after K pops. Seed the heap with the first element of each row (or only the first min(n, k) rows), pop K-1 times pushing the right neighbour each time, and the root is the answer. Time O(k log n). Mention the alternative: binary search on the answer over the value range, counting elements ≤ mid in O(n) per step, giving O(n log(max - min)).

Smallest Range Covering Elements from K Lists (LeetCode 632)

The hard-level K-way merge. Keep one pointer per list in a min-heap and track the current maximum among the pointers. The range [heap.min, curMax] always contains one element from every list. Pop the min, update the best range, advance that list and update curMax. Stop as soon as any list is exhausted, because then no range can include that list any more. Time O(N log K).

import heapq

def smallest_range(nums):
    heap = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(heap)
    cur_max = max(row[0] for row in nums)
    best = (-10**9, 10**9)
    while True:
        lo, i, j = heapq.heappop(heap)
        if cur_max - lo < best[1] - best[0]:
            best = (lo, cur_max)
        if j + 1 == len(nums[i]):
            return list(best)
        nxt = nums[i][j + 1]
        cur_max = max(cur_max, nxt)
        heapq.heappush(heap, (nxt, i, j + 1))

Pattern 3: Two Heaps for the Running Median

Find Median from Data Stream (LeetCode 295) is the canonical two-heaps question and one of the most frequently reported heap problems in Amazon, Microsoft and Google loops. The idea: split the numbers into a lower half and an upper half.

• low: a max-heap holding the smaller half. Its top is the largest of the small numbers.
• high: a min-heap holding the larger half. Its top is the smallest of the large numbers.
• Invariants: every element of low ≤ every element of high, and len(low) equals len(high) or exceeds it by exactly one.

The median is then low.top (odd count) or the average of both tops (even count). The cleanest way to maintain both invariants: always push into low, move low's top to high, and if high got bigger, move its top back.

class MedianFinder {
    private final PriorityQueue<Integer> low =
        new PriorityQueue<>(Collections.reverseOrder());   // max-heap
    private final PriorityQueue<Integer> high = new PriorityQueue<>(); // min-heap

    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());              // largest of low moves up
        if (high.size() > low.size()) {
            low.offer(high.poll());          // rebalance: low may hold one extra
        }
    }

    public double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return (low.peek() + (long) high.peek()) / 2.0;
    }
}

class MedianFinder {
    priority_queue<int> low;                                    // max-heap
    priority_queue<int, vector<int>, greater<int>> high;       // min-heap
public:
    void addNum(int num) {
        low.push(num);
        high.push(low.top());
        low.pop();
        if (high.size() > low.size()) {
            low.push(high.top());
            high.pop();
        }
    }
    double findMedian() {
        if (low.size() > high.size()) return low.top();
        return ((long long)low.top() + high.top()) / 2.0;
    }
};

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []    # max-heap via negation
        self.high = []   # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

Dry run for the stream 5, 15, 1, 3:

1. Add 5. low=[5] → move 5 to high → high bigger, move back. low=[5], high=[]. Median 5.
2. Add 15. low=[15,5] → move 15 to high. low=[5], high=[15]. Sizes equal. Median (5+15)/2 = 10.
3. Add 1. low=[5,1] → move 5 to high. low=[1], high=[5,15] → high bigger, move 5 back. low=[5,1], high=[15]. Median 5.
4. Add 3. low=[5,3,1] → move 5 to high. low=[3,1], high=[5,15]. Median (3+5)/2 = 4. Check: sorted [1,3,5,15], median 4. Correct.

Each addNum does up to three heap operations, so O(log n); findMedian is O(1). Note the long cast: two values near Integer.MAX_VALUE overflow when added as ints.

Follow-ups interviewers ask on the median problem

• "All numbers are in [0, 100]." Use a count array of size 101 and walk it to find the middle: O(1) insert, O(100) median.
• "99% of numbers are in [0, 100]." Count array for the range plus two small heaps (or counters) for outliers below and above.
• "Median of a sliding window." Now you must remove elements leaving the window, which needs lazy deletion (Pattern 5) or a balanced BST / SortedList.
• "Distributed stream across many machines." Exact median needs coordination; mention approximate quantile sketches such as t-digest. This shows breadth without derailing the round.

The two-heaps idea generalises beyond medians. IPO (LeetCode 502) uses a min-heap of projects by capital required and a max-heap of affordable projects by profit: unlock everything you can afford, take the most profitable, repeat K times.

Pattern 4: Greedy Scheduling with a Heap

Many greedy algorithms say "at each step, take the best available option", and the set of available options changes over time. A heap is the natural engine. If you want the reasoning behind why greedy works on these, read how to know when greedy works.

Meeting Rooms II (LeetCode 253)

Sort meetings by start time. Keep a min-heap of end times of meetings currently occupying rooms. For each meeting, if the earliest-ending room is free (heap.top ≤ start), reuse it by popping; then push this meeting's end. The heap size at the end (or its maximum size) is the number of rooms.

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>();
    for (int[] m : intervals) {
        if (!ends.isEmpty() && ends.peek() <= m[0]) {
            ends.poll();                 // reuse the room that frees up first
        }
        ends.offer(m[1]);
    }
    return ends.size();
}

O(n log n). The line-sweep alternative (sort starts and ends separately, two pointers) has the same complexity and is worth mentioning. More interval variants are in the intervals interview problems guide.

Task Scheduler and Reorganize String

Reorganize String (LeetCode 767): rearrange so no two adjacent characters are equal. Greedy: always place the most frequent remaining character that is not the one just placed. Implementation: max-heap of (count, char); pop the top, append it, and hold it aside for one step so it cannot be chosen next; then push back the previously held character if its count is still positive.

import heapq
from collections import Counter

def reorganize_string(s):
    heap = [(-cnt, ch) for ch, cnt in Counter(s).items()]
    heapq.heapify(heap)
    out = []
    prev = None                      # (neg_count, char) waiting one turn
    while heap:
        cnt, ch = heapq.heappop(heap)
        out.append(ch)
        if prev and prev[0] < 0:
            heapq.heappush(heap, prev)
        prev = (cnt + 1, ch)         # one fewer remaining (counts are negative)
    return "".join(out) if len(out) == len(s) else ""

Task Scheduler (LeetCode 621) generalises the cooldown to n. You can simulate with a max-heap plus a queue of (count, ready_time), but there is a well-known closed form: with maxFreq the highest frequency and maxCount the number of tasks having it, the answer is max(len(tasks), (maxFreq - 1) * (n + 1) + maxCount). Give the heap simulation first (it is easier to justify), then the formula as an optimisation.

Minimum Cost to Connect Sticks / Huffman-style merging

Always merge the two smallest. Pop two, push their sum, add the sum to the cost. This is exactly Huffman coding's construction and is optimal by an exchange argument: the two smallest items should be deepest in the merge tree. O(n log n).

Pattern 5: Lazy Deletion and Heaps in Graph Algorithms

Standard binary heaps cannot efficiently delete an arbitrary element or decrease a key. Two interview-friendly workarounds cover almost every case.

Lazy deletion for sliding window median

In Sliding Window Median (LeetCode 480), elements leave the window from the middle of the heaps. Instead of removing them immediately, record them in a hash map delayed[value] += 1 and keep a "logical size" for each heap. Whenever an element with a pending deletion reaches the top of a heap, pop it and decrement the map. Because you only ever read tops, stale elements buried inside the heap never affect answers. Each element is pushed and popped at most once, so the total is O(n log n).

Dijkstra: duplicates instead of decrease-key

Textbook Dijkstra uses decrease-key. In interviews, push a new (dist, node) pair whenever you find a shorter distance, and when you pop a pair whose distance is larger than the recorded best, skip it. The heap can hold up to O(E) entries, so the complexity is O(E log E), which equals O(E log V) since E ≤ V². The full treatment, including when Dijkstra fails, is in shortest path algorithms explained.

int[] dijkstra(List<int[]>[] adj, int src) {
    int n = adj.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;            // stale entry: lazy deletion
        for (int[] e : adj[u]) {
            int v = e[0], w = e[1];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

Heap Complexity Cheat Sheet

Heap sort is worth a sentence: build a max-heap in place, swap the root to the end, shrink, sift down, repeat. It is O(n log n) worst case and O(1) extra space, but it is not stable and has poor cache locality, which is why library sorts prefer introsort or Timsort. The sorting algorithms comparison goes deeper.

How Interviewers Probe Heap Solutions

Writing a correct heap solution is the baseline. What separates a "hire" from a "strong hire" is how you handle the conversation around it. In mock interviews I see candidates write a perfect mergeKLists and then stumble on the follow-ups below. Prepare an answer for each.

Also be ready to justify the space complexity precisely. "O(k) for the heap plus O(m) for the frequency map" sounds far stronger than "O(n)". And when you choose between a heap and a balanced BST (TreeMap, std::multiset), say why: the BST supports deletion of arbitrary elements and in-order iteration in O(log n), at a higher constant factor. For sliding window median, multiset in C++ is often the cleanest solution.

A good habit, covered in thinking out loud in coding interviews: before coding, state the invariant your heap maintains ("the heap holds the K largest seen so far; its root is the Kth largest"). Interviewers can then verify your code against the invariant instead of guessing your intent.

Common Heap Bugs (and How to Avoid Them)

• Uncomparable tuples in Python. heappush(h, (node.val, node)) throws TypeError when two values tie, because Python then compares the ListNode objects. Insert a unique index or counter as the second element.
• Inverted C++ comparators. In priority_queue, the comparator returning a > b yields a min-heap. If you write a custom struct, test with three elements before trusting it.
• Calling top() or peek() on an empty heap. C++ is undefined behaviour; Java returns null and then throws on unboxing. Guard every access.
• Forgetting that C++ pop() returns void. Read top() first.
• Mutating an object after inserting it. If you change the priority field of an object already in a Java PriorityQueue, the heap does not re-sort it. Remove and reinsert, or push a new entry and use lazy deletion.
• Using the wrong heap direction for Top-K. A max-heap of all n elements popped K times is O(n + k log n): correct, but not the O(k)-space streaming answer the interviewer wants.
• Iterating a heap and expecting sorted order. Iterating Java's PriorityQueue or Python's list walks the array, which is not sorted. Pop repeatedly instead.

Heap Practice List: 15 Problems in Order

Work through these in order; each one adds one new idea. If you are building a full plan around them, the top DSA patterns guide shows where heaps fit relative to graphs and DP.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.