← Back to DevBytes
Developer Tutorial July 12, 2026 14 min read

Interview Guide: Heaps Problems and Solutions

Interview Guide: Heaps Problems and Solutions

A heap is a specialized tree-based data structure that satisfies the heap property. In a min-heap, the parent node is always smaller than or equal to its children. In a max-heap, the parent node is always greater than or equal to its children. Heaps are the go-to structure when you need efficient access to the minimum or maximum element in a dynamically changing dataset.

Why Heaps Matter in Technical Interviews

Heap problems appear with remarkable frequency in coding interviews at companies like Google, Meta, Amazon, and Microsoft. Interviewers love them because they test multiple skills simultaneously:

Mastering heaps signals to the interviewer that you can optimize beyond naive O(n log n) sorting solutions and handle streaming or online data gracefully.

Core Heap Operations

Every heap problem builds on these fundamental operations. Knowing their complexities cold is essential:

Language-Specific Heap Implementations

Different languages expose heaps differently. Here are the standard approaches you should have memorized for your interview language.

Python — heapq (Min-Heap by Default)

import heapq

# Python's heapq is a min-heap. For max-heap, negate values.
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 9)

# Peek at smallest element
smallest = min_heap[0]  # 1

# Pop smallest
while min_heap:
    print(heapq.heappop(min_heap))  # 1, 3, 5, 9

# Heapify an existing list in O(n)
arr = [7, 2, 4, 1, 8]
heapq.heapify(arr)
print(arr[0])  # 1 (min element)

# Max-heap using negation
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
largest = -max_heap[0]  # 10
popped = -heapq.heappop(max_heap)  # 10

# For custom objects, use tuples: (priority, item)
# The heap compares tuple elements in order
tasks = []
heapq.heappush(tasks, (2, 'task_a'))
heapq.heappush(tasks, (1, 'urgent_task'))
heapq.heappop(tasks)  # (1, 'urgent_task') — lower priority number = higher urgency

# Custom comparator alternative: use a wrapper class with __lt__
class Wrapper:
    def __init__(self, val, priority):
        self.val = val
        self.priority = priority
    def __lt__(self, other):
        return self.priority < other.priority

custom_heap = []
heapq.heappush(custom_heap, Wrapper("A", 5))
heapq.heappush(custom_heap, Wrapper("B", 2))
heapq.heappop(custom_heap).val  # "B"

Java — PriorityQueue

import java.util.PriorityQueue;
import java.util.Comparator;

// Default: min-heap (natural ordering)
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(1);
minHeap.add(3);

// Peek smallest
int smallest = minHeap.peek();  // 1
// Poll smallest
int popped = minHeap.poll();    // 1

// Max-heap: custom comparator
PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.add(5);
maxHeap.add(10);
int largest = maxHeap.peek();   // 10

// Custom comparator for objects
class Task {
    String name;
    int priority;
    Task(String n, int p) { name = n; priority = p; }
}
PriorityQueue taskHeap = new PriorityQueue<>((t1, t2) -> t1.priority - t2.priority);
taskHeap.add(new Task("urgent", 1));
taskHeap.add(new Task("normal", 5));

// Alternative: Comparator.comparingInt
PriorityQueue heap2 = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));

JavaScript — No Built-in Heap (DIY or Library)

// JavaScript has no native heap. You must implement one or use a library.
// Here's a minimal min-heap implementation for interviews:

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    size() { return this.heap.length; }
    peek() { return this.heap[0]; }
    
    push(val) {
        this.heap.push(val);
        this._bubbleUp(this.heap.length - 1);
    }
    
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._sinkDown(0);
        return root;
    }
    
    _bubbleUp(idx) {
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[idx] >= this.heap[parentIdx]) break;
            [this.heap[idx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[idx]];
            idx = parentIdx;
        }
    }
    
    _sinkDown(idx) {
        const length = this.heap.length;
        const element = this.heap[idx];
        while (true) {
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let swapIdx = null;
            
            if (leftChildIdx < length && this.heap[leftChildIdx] < element) {
                swapIdx = leftChildIdx;
            }
            if (rightChildIdx < length) {
                if ((swapIdx === null && this.heap[rightChildIdx] < element) ||
                    (swapIdx !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])) {
                    swapIdx = rightChildIdx;
                }
            }
            
            if (swapIdx === null) break;
            [this.heap[idx], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[idx]];
            idx = swapIdx;
        }
    }
}

// Usage:
const heap = new MinHeap();
heap.push(5);
heap.push(1);
heap.push(3);
console.log(heap.peek());  // 1
console.log(heap.pop());   // 1
console.log(heap.pop());   // 3

// For max-heap, negate values or modify comparisons

C++ — priority_queue

#include 
#include 
#include 

// Default: max-heap (largest element on top)
std::priority_queue maxHeap;
maxHeap.push(5);
maxHeap.push(10);
maxHeap.push(3);
int top = maxHeap.top();  // 10
maxHeap.pop();

// Min-heap: use greater comparator
std::priority_queue, std::greater> minHeap;
minHeap.push(5);
minHeap.push(10);
minHeap.push(3);
int minTop = minHeap.top();  // 3

// Custom comparator with lambdas (C++11+)
auto cmp = [](const std::pair& a, const std::pair& b) {
    return a.second > b.second;  // min-heap based on second element
};
std::priority_queue, 
                    std::vector>, 
                    decltype(cmp)> customHeap(cmp);

customHeap.push({1, 5});
customHeap.push({2, 3});
customHeap.top();  // {2, 3} — because 3 < 5

Classic Interview Problem Patterns

Heap problems in interviews typically fall into several well-defined patterns. Recognizing these patterns quickly will save you precious minutes during the interview.

Pattern 1: Top-K Elements

The most common heap pattern. Given a collection, find the K largest or K smallest elements. The key insight: maintain a heap of size K — a min-heap for K largest, or a max-heap for K smallest.

Example: Kth Largest Element in an Array

# LeetCode 215: Kth Largest Element in an Array
# Strategy: Min-heap of size K. After processing all elements,
# the root of the min-heap is the Kth largest.

import heapq

def findKthLargest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

# Time: O(n log k) — each push/pop is O(log k), done n times
# Space: O(k)
# Compare to sorting: O(n log n) time — heap wins when k << n

print(findKthLargest([3,2,1,5,6,4], 2))  # 5
print(findKthLargest([3,2,3,1,2,4,5,5,6], 4))  # 4

Example: Top K Frequent Elements

# LeetCode 347: Top K Frequent Elements
# Count frequencies, then use min-heap of size K on frequencies

import heapq
from collections import Counter

def topKFrequent(nums, k):
    freq = Counter(nums)
    heap = []
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for count, num in heap]

# Alternative: use bucket sort for O(n) when k is arbitrary
# But heap approach is cleaner and O(n log k)
print(topKFrequent([1,1,1,2,2,3], 2))  # [1, 2]

Pattern 2: K-Way Merge

Merge multiple sorted arrays or streams into one sorted output. A min-heap extracts the smallest current element among all streams, then advances the pointer in that stream. Classic problem: Merge K Sorted Lists.

# LeetCode 23: Merge K Sorted Lists
# Definition for singly-linked list (conceptual):
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

import heapq

def mergeKLists(lists):
    heap = []
    # Push the head of each list with a tie-breaker index
    # (index prevents comparing ListNode objects if vals are equal)
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    
    dummy = ListNode(0)
    curr = dummy
    
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

# Time: O(N log k) where N = total nodes, k = number of lists
# Space: O(k) for the heap

Pattern 3: Two Heaps (Median Tracking)

Maintain two heaps — a max-heap for the lower half and a min-heap for the upper half — to track the median of a stream. This pattern appears in "Find Median from Data Stream" and similar scheduling problems.

# LeetCode 295: Find Median from Data Stream
import heapq

class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap (negated values)
        self.high = []  # min-heap
    
    def addNum(self, num):
        # Always push to low first (max-heap of lower half)
        heapq.heappush(self.low, -num)
        
        # Balance: move largest of low to high
        heapq.heappush(self.high, -heapq.heappop(self.low))
        
        # Maintain size property: low can have at most 1 more than high
        if len(self.low) < len(self.high):
            heapq.heappush(self.low, -heapq.heappop(self.high))
    
    def findMedian(self):
        if len(self.low) > len(self.high):
            return -self.low[0]  # odd count, median is top of low
        else:
            return (-self.low[0] + self.high[0]) / 2.0

mf = MedianFinder()
mf.addNum(1)
mf.addNum(2)
print(mf.findMedian())  # 1.5
mf.addNum(3)
print(mf.findMedian())  # 2.0

# Time: addNum is O(log n), findMedian is O(1)
# Space: O(n)

Pattern 4: Scheduling and Task Management

When tasks have frequencies, deadlines, or cooldowns, heaps help prioritize what to process next. Common examples: Task Scheduler, Meeting Rooms II, CPU scheduling.

# LeetCode 621: Task Scheduler
# Given tasks array and cooldown n, find minimum time to complete all tasks.
# Approach: max-heap by frequency, then cooldown queue.

import heapq
from collections import Counter, deque

def leastInterval(tasks, n):
    freq = Counter(tasks)
    max_heap = [-count for count in freq.values()]
    heapq.heapify(max_heap)
    
    time = 0
    queue = deque()  # (next_available_time, -count)
    
    while max_heap or queue:
        time += 1
        
        if max_heap:
            count = heapq.heappop(max_heap) + 1  # +1 because negative
            if count < 0:
                queue.append((time + n, count))
        
        if queue and queue[0][0] == time:
            _, count = queue.popleft()
            heapq.heappush(max_heap, count)
    
    return time

print(leastInterval(["A","A","A","B","B","B"], 2))  # 8

Pattern 5: Dijkstra's Algorithm with Heaps

Shortest path in weighted graphs relies on a min-heap to extract the next closest node efficiently. This is a fundamental graph algorithm that every candidate should know.

# Dijkstra's Algorithm for shortest path from source to all nodes
import heapq

def dijkstra(graph, start):
    # graph: adjacency list {node: [(neighbor, weight), ...]}
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]  # (distance, node)
    visited = set()
    
    while heap:
        dist, node = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return distances

# Example usage
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('D', 3)],
    'D': []
}
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 4, 'C': 2, 'D': 5}

Advanced Heap Techniques

Custom Comparators for Complex Data

When sorting by multiple criteria (e.g., frequency then alphabetical order), craft your comparator or tuple ordering carefully. In Python, tuples are compared lexicographically — the first differing element determines the order.

# Multi-criteria ordering: primary by frequency (desc), secondary by word (asc)
# For min-heap with frequency descending: use (-freq, word)
import heapq

words = [("apple", 3), ("banana", 3), ("cherry", 1), ("date", 5)]
heap = []
for word, freq in words:
    heapq.heappush(heap, (-freq, word))

# Pop yields highest frequency first, then alphabetically
while heap:
    freq_neg, word = heapq.heappop(heap)
    print(f"{-freq_neg}: {word}")
# Output: 5: date, 3: apple, 3: banana, 1: cherry

Lazy Deletion / Heap with Removal

Sometimes you need to update or remove arbitrary elements from a heap. Since heaps don't support O(log n) arbitrary removal natively, use a "lazy deletion" strategy: mark elements as invalid and skip them when they bubble to the top.

# Lazy deletion pattern: keep a "to_remove" counter/map
# When popping, skip elements that should be removed
import heapq
from collections import Counter

class RemovableHeap:
    def __init__(self):
        self.heap = []
        self.to_remove = Counter()
        self.size = 0
    
    def push(self, val):
        heapq.heappush(self.heap, val)
        self.size += 1
    
    def remove(self, val):
        """Lazy removal: mark val for later skipping"""
        self.to_remove[val] += 1
        self.size -= 1
    
    def pop(self):
        """Pop and skip lazily removed elements"""
        while self.heap:
            val = heapq.heappop(self.heap)
            if self.to_remove[val] > 0:
                self.to_remove[val] -= 1
            else:
                self.size -= 1
                return val
        return None
    
    def peek(self):
        while self.heap and self.to_remove[self.heap[0]] > 0:
            val = heapq.heappop(self.heap)
            self.to_remove[val] -= 1
        return self.heap[0] if self.heap else None

# Useful for sliding window median or problems requiring heap updates

Heap of Tuples — Avoiding Comparison Failures

When pushing tuples onto a heap, if the first elements are equal, Python compares the second elements. If the second elements are incomparable (e.g., custom objects), the comparison fails. The fix: insert a unique tie-breaker like an incrementing counter or index.

# Safe tuple pattern with tie-breaker
import heapq
import itertools

counter = itertools.count()
heap = []
heapq.heappush(heap, (priority, next(counter), complex_object))
# The counter ensures no two tuples are identical,
# preventing comparison of complex_object

Common Pitfalls and How to Avoid Them

Best Practices for Heap Interviews

Mock Interview Walkthrough: "Find the K Closest Points to Origin"

Here's a complete interview simulation demonstrating how to approach a heap problem from start to finish.

# Problem: Given an array of points [x, y] and an integer K,
# return the K closest points to the origin (0, 0).
# Distance = sqrt(x² + y²), but we can compare squared distances.

import heapq

def kClosest(points, k):
    # We need the K smallest distances, so use a MAX-heap
    # (counter-intuitive! Because we want to KEEP the closest,
    #  we discard the farthest from our heap)
    # Actually, cleaner approach: min-heap of all points, then pop K
    # But for streaming/large data, max-heap of size K is better.
    
    # Max-heap of size K: store (-distance, point)
    max_heap = []
    for x, y in points:
        dist = x*x + y*y
        # Push negative distance for max-heap behavior
        heapq.heappush(max_heap, (-dist, [x, y]))
        if len(max_heap) > k:
            heapq.heappop(max_heap)
    
    return [point for _, point in max_heap]

# Alternative: min-heap of all, pop K — simpler but O(n) space
def kClosest_simple(points, k):
    heap = [(x*x + y*y, [x, y]) for x, y in points]
    heapq.heapify(heap)  # O(n)
    return [heapq.heappop(heap)[1] for _ in range(k)]

print(kClosest([[1,3], [-2,2], [2,1], [3,4]], 2))  # [[-2,2], [2,1]]
print(kClosest_simple([[1,3], [-2,2], [2,1], [3,4]], 2))  # [[-2,2], [2,1]]

During the interview, you'd walk through this step by step: clarify the distance metric, choose between the two heap strategies, explain the O(n log k) vs O(n) heapify tradeoff, handle the K=0 edge case, and test with sample coordinates.

Additional Practice Problems

Here is a curated list of high-frequency heap problems to work through before your interview. Each maps to the patterns described above.

Conclusion

Heaps are one of the most versatile and frequently tested data structures in technical interviews. By internalizing the core patterns — top-K, K-way merge, two-heap median tracking, and priority-based scheduling — you equip yourself with a powerful toolkit that transforms O(n log n) problems into elegant O(n log k) solutions. The key to success is not just memorizing heap syntax, but deeply understanding when a heap is the right tool: whenever you need repeated access to the minimum or maximum element in a dynamic collection. Practice the language-specific APIs until they're muscle memory, master the edge cases and pitfalls, and you'll approach any heap problem with confidence and clarity.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles