LiveCodingInterview.com
← Articles

Heap Interview Questions: How to Recognize and Solve Them

A heap interview question is really testing one thing: do you reach for a structure that keeps giving you the smallest or largest remaining item in O(log n), instead of sorting a list you only need part of. Once you see the phrase "k largest", "k closest", or "merge k sorted", a heap should be the first structure you consider, not the third one you try after a sort and a brute-force pass both feel too slow. This piece covers how to spot the pattern from the wording alone, how the structure works under the hood, full walkthroughs of the two problems that show up most in real loops, and the follow-up interviewers almost always ask once your first solution works.

What Is a Heap, and Why Do Interviewers Ask About It?

A heap is a tree-shaped structure that keeps one guarantee at all times: every parent node is smaller than its children in a min-heap, or larger in a max-heap. That single rule, checked only between a node and its direct children, is what makes a heap cheap to maintain and fast to query. You don't get a fully sorted list out of it, and that's the point: a heap trades full ordering, which costs O(n log n) to build, for a narrower guarantee, always knowing the smallest or largest element instantly, at only O(log n) to maintain as the data changes.

Interviewers reach for heap questions because they sit at a clean intersection of theory and judgment. Implementing one from scratch checks whether you understand array-based trees and recursion, and recognizing when to use one instead of a sort checks something closer to engineering taste: whether you notice a problem only cares about the top k elements out of n, and that sorting all n when you only need k wastes real work. That second skill is usually worth more than the implementation itself, since most candidates can code a heap once they know to reach for it.

How Do You Recognize a Heap Problem in an Interview?

You recognize a heap problem from a small set of phrases that show up in the prompt, and once you've seen them a few times, spotting them stops taking real thought.

Watch for these signals in the problem statement:

  • the question asks for the k largest, k smallest, or k closest elements, not the full sorted order
  • you need repeated access to the current minimum or maximum while the underlying data keeps changing
  • the problem describes merging several already-sorted streams or lists into one
  • there's a notion of scheduling or processing items by priority rather than by arrival order
  • the input is described as a stream or is too large to sort in one pass, but you only need a small, bounded piece of it

The "k" signal is the strongest one on its own. Any prompt with a k in it, k largest, k closest, kth smallest, top k frequent, is worth testing against a heap before anything else, since a heap turns a full O(n log n) sort into an O(n log k) pass that only tracks the k elements that currently matter. That gap is small on a whiteboard-sized example and enormous on the input sizes these problems are actually testing.

How Does a Heap Actually Work Under the Hood?

A heap is almost always implemented as an array, not as an actual tree of linked nodes, and the tree shape lives entirely in how you compute indices. For a node stored at index i, its children sit at 2i + 1 and 2i + 2, and its parent sits at (i - 1) // 2. A complete binary tree, one with no gaps except possibly at the bottom right, maps perfectly onto a flat array with no pointers needed.

Two operations keep the heap property intact. Inserting a new element adds it to the end of the array, then bubbles it upward, swapping with its parent, for as long as it's smaller than that parent in a min-heap. Removing the top element swaps the last element into the root's position, shrinks the array by one, then sifts that element downward until both children are no longer smaller than it. Both operations only ever touch one path between a node and the root, which is why each runs in O(log n).

Here's a minimal min-heap in Python, built on nothing but a list, to make the index math concrete:

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

    def push(self, val):
        self.data.append(val)
        self._bubble_up(len(self.data) - 1)

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

    def _bubble_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self.data[parent] <= self.data[i]:
                break
            self.data[parent], self.data[i] = self.data[i], self.data[parent]
            i = parent

    def _sift_down(self, i):
        n = len(self.data)
        while True:
            smallest = i
            left, right = 2 * i + 1, 2 * i + 2
            if left < n and self.data[left] < self.data[smallest]:
                smallest = left
            if right < n and self.data[right] < self.data[smallest]:
                smallest = right
            if smallest == i:
                break
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            i = smallest

In an actual interview, you'd almost never write this from scratch. Python's heapq module, Java's PriorityQueue, and C++'s priority_queue all give you a working heap out of the box, and using one is expected rather than penalized. Interviewers want to know it exists, hear the operations named as you call them, and get the array indexing above explained if they ask how the built-in actually works.

One misconception worth clearing up directly: building a heap from an existing array of n elements does not cost O(n log n), even though pushing n elements one at a time would. The standard build-heap algorithm starts from the last non-leaf node and sifts each one downward, and because most nodes in a complete tree sit near the bottom where a sift-down barely moves anything, the total work sums to O(n). Naming that correctly out loud is a small, cheap signal that you understand the structure rather than having memorized its use cases.

What Is the Time Complexity of Heap Operations?

The complexity of every core heap operation follows directly from the fact that each one only ever walks a single root-to-leaf or leaf-to-root path.

| Operation | Time complexity | Why | | --- | --- | --- | | Peek min or max | O(1) | Always sits at index 0 | | Insert | O(log n) | Bubbles up at most the tree height | | Remove min or max | O(log n) | Sifts down at most the tree height | | Build heap from array | O(n) | Bottom-up sift-down, most nodes near the bottom | | Search for an arbitrary value | O(n) | No ordering guarantee outside the parent-child rule |

That last row is the one candidates trip over most. A heap gives you no shortcut for finding an arbitrary value, only the current minimum or maximum. If a problem needs fast search or update of an arbitrary element, a heap alone is the wrong tool, and reaching for one anyway usually means you matched the word "priority" without checking whether the rest of the requirements fit.

How Do You Solve "K Closest Points to Origin" With a Heap?

K Closest Points to Origin asks for the k points nearest the origin out of a list of n points, and it's one of the two heap problems most likely to show up in a real loop, since it maps the "k closest" signal onto a heap almost exactly as written.

Compute each point's squared distance from the origin, skipping the square root since it doesn't change the ordering, then maintain a max-heap of size k. Push each point's distance and coordinates onto the heap, and whenever it grows past size k, pop the largest element off, since it's now guaranteed to be farther than at least k other points already seen. Once every point is processed, whatever remains in the heap is exactly the k closest points, in no particular order.

import heapq

def k_closest(points, k):
    heap = []
    for x, y in points:
        dist = -(x * x + y * y)
        if len(heap) < k:
            heapq.heappush(heap, (dist, x, y))
        elif dist > heap[0][0]:
            heapq.heapreplace(heap, (dist, x, y))
    return [(x, y) for dist, x, y in heap]

Python's heapq only implements a min-heap, so negating the distance before pushing turns "pop the largest" into "pop the smallest of the negated values". That trick is worth saying out loud the moment you use heapq for a max-heap problem, since an interviewer watching you negate a value without explaining it can read it as a mistake instead of a deliberate move.

This runs in O(n log k) time and O(k) space, against O(n log n) for sorting the full list and slicing the first k. The gap matters most when k is small relative to n, tracking the 5 closest points out of a million rather than fully sorting all of them.

How Do You Solve "Merge K Sorted Lists" With a Heap?

Merge K Sorted Lists asks you to combine k already-sorted linked lists into one fully sorted list, the clearest example of the "merging several sorted streams" signal from earlier and the second problem worth having fully solved before a real interview.

The naive approach compares the current head of all k lists on every step to find the minimum, costing O(k) per element and O(nk) overall. A heap collapses that per-step cost from O(k) to O(log k): push the head of each list onto a min-heap, pop the smallest, and push whatever node followed it in that same list back onto the heap.

import heapq

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = tail = ListNode()
    while heap:
        val, 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

The list index i in each tuple exists purely to break ties. Python compares tuples element by element, and if two nodes share the same value, it would try to compare the ListNode objects directly, which raises an error since nodes aren't comparable. A unique index guarantees the comparison never reaches that point, worth mentioning as you write it so it reads as deliberate rather than accidental.

This runs in O(n log k) time, where n is the total number of nodes across every list, and O(k) space for the heap. The result is one sorted list built in a single pass, without holding more than k candidate nodes in memory at once.

What Follow-Up Questions Do Interviewers Ask After the Base Heap Solution?

Once your first heap solution works, the most common follow-up shifts the problem from a fixed array to a stream you can't hold in memory all at once, and it's worth having an answer ready rather than improvising one live.

For K Closest Points, the natural escalation is "what if the points arrive one at a time and you can't store them all?" The heap-of-size-k approach already answers this without changing a line, since it never needed the full input in memory, only a running window of the k best candidates seen so far. Pointing that out directly signals you understood why you built it that way rather than getting lucky.

For Merge K Sorted Lists, the usual escalation is "what if k is very large, in the thousands, and rebalancing the heap on every pop becomes the bottleneck?" That's the moment to mention a pairwise merge that combines lists two at a time, doubling the merged result at each round, which trades a different constant factor for the same O(n log k) bound. You aren't expected to code that alternative live in most loops, but naming it shows the heap-based approach isn't the only shape this problem can take.

A third follow-up ties back to array and substring problems: what if you only need the k largest elements from a sliding window as it moves across the input? That's the same k-tracking idea from K Closest Points, applied to a moving range instead of a fixed list, and spotting the combination is what separates memorizing two solutions from understanding why both work.

When Should You NOT Reach for a Heap?

A heap is the wrong tool more often than the "k largest" signal suggests, and naming the cases where you'd skip one is worth more than reflexively reaching for a priority queue every time a problem mentions ordering.

Skip the heap when k is close to n. If a problem asks for the 900,000 largest elements out of a million, a full sort at O(n log n) beats a heap-based O(n log k) approach in practice, since log k and log n end up nearly identical and the sort avoids the heap's extra bookkeeping. Skip it too when the data is already sorted, since a two-pointer or binary search approach over sorted input usually beats maintaining a heap you didn't need, and skip it when the problem needs fast lookup or update of an arbitrary element rather than just the current minimum or maximum, since a balanced tree or a hash map paired with lazy deletion is the better fit there.

Saying "a heap would work here, but a straight sort is simpler and just as fast at this k" reads as stronger judgment than defaulting to the more complex structure just because the problem mentioned a ranking.

How Do You Talk Through a Heap Solution in an Interview?

Name the signal before you write any code. Saying "this asks for the k closest points, so I'm reaching for a heap instead of sorting everything" out loud, before your hands touch the keyboard, tells the interviewer you recognized the pattern rather than stumbled into the right structure by trial and error. Follow it by stating which kind of heap you need and why, since "I need a max-heap here so I can compare the current farthest point against a new one" gives the interviewer something to follow that silent code never does. If you're faking a max-heap by negating values, say so the moment you do it.

Then walk through the complexity comparison against the naive approach, not just the final Big O. "Sorting the whole list would cost O(n log n), but since I only need the top k, a heap gets that down to O(n log k)" shows you considered the alternative and chose deliberately, the same habit our guide to time complexity in interviews covers for every other structure.

Where to Practice Heap Problems Next

K Closest Points to Origin and Merge K Sorted Lists cover the two shapes that show up most, but the same heap-of-size-k idea extends to Top K Frequent Elements, Kth Largest Element in an Array, and Find Median from a Data Stream, which pairs a max-heap with a min-heap to keep two halves of a running dataset balanced. Once the base pattern is automatic, those three are mostly the same template with a different comparison key.

Our curated question bank pulls heap and priority-queue problems from real onsite reports instead of an unfiltered public archive, so the versions you practice match what loops are actually asking rather than problems that stopped showing up years ago. Pair this with pattern recognition across the rest of the coding round so a heap becomes one identifiable shape among several the moment you see "k largest" or "merge sorted streams" in a prompt, instead of a structure you only remember once someone points it out.

Frequently Asked Questions

What is a heap in coding interviews?

A heap is a tree-shaped structure, almost always implemented as an array, that keeps the smallest element at the top in a min-heap or the largest in a max-heap. It gives O(1) access to that top element and O(log n) insert and remove, the standard combination for any problem centered on repeatedly finding a current minimum or maximum as data changes.

What is the time complexity of building a heap from an array?

Building a heap from an existing array of n elements takes O(n), not O(n log n). The bottom-up build-heap algorithm sifts each non-leaf node downward starting from the last one, and since most nodes sit near the bottom of the tree where a sift-down barely moves anything, the total cost across every node sums to linear time.

Is a heap the same as a priority queue?

Close, but the two terms aren't quite interchangeable. A priority queue is the abstract idea, always give me the highest-priority item next, and a heap is the most common structure used to implement it, though a priority queue could technically run on a sorted array or a balanced tree instead. Most languages build their priority queue library directly on top of a heap.

What are the most common heap interview problems?

K Closest Points to Origin, Merge K Sorted Lists, Top K Frequent Elements, Kth Largest Element in an Array, and Find Median from a Data Stream cover most of what shows up in real loops. All of them reduce to the same idea: maintain a heap sized around k, and adjust what you push, pop, and compare based on the question.

Can you use a heap to find the median of a data stream?

Yes, by keeping two heaps balanced against each other: a max-heap holding the smaller half of the numbers seen so far, and a min-heap holding the larger half. Keeping both halves within one element of each other means the median is always either the top of one heap or the average of both tops, without sorting the full stream.