Heaps and Priority Queues — Complete Interview Guide

Problem Statement#

A heap is a complete binary tree where every parent satisfies the heap property with its children. Heaps power priority queues, the data structure behind nearly every Top-K, streaming median, and k-way merge interview problem at FAANG.

Constraints:

• Insert: O(log n)
• Pop top: O(log n)
• Peek top: O(1)
• Build heap from array: O(n)

Min-heap: parent <= children, root = smallest
Max-heap: parent >= children, root = largest

Array layout (1-indexed for math):
parent(i) = i / 2
left(i)   = 2 * i
right(i)  = 2 * i + 1

Why This Problem Matters#

Heaps appear in nearly every senior FAANG interview loop. Google, Meta, Amazon, and Microsoft routinely ask priority-queue problems like Kth Largest, Top K Frequent, Median of Data Stream, and Merge K Sorted Lists. If you can recognize the heap pattern in 30 seconds, you instantly cut the search space of brute-force solutions.

The reason heaps dominate "online" and "streaming" questions is that they trade total ordering for partial ordering: you only need the extremum, not a fully sorted structure. That subtle insight is often the difference between an O(n log n) sort and an O(n log k) heap solution.

Keywords interviewers use to hint at heaps: "top K", "K closest", "K most frequent", "median of stream", "merge K sorted", "schedule", "smallest range", and "meeting rooms".

The Core Insight#

A heap gives you O(1) access to the min or max while maintaining O(log n) inserts and removals. When a problem only cares about the extremum (or the K extremes), a heap beats sorting. When a problem mixes streaming insertions with extremum queries, a heap is almost always optimal.

Visual Dry Run#

Language Heap APIs#

import heapq
h = []
heapq.heappush(h, val)
heapq.heappop(h)
h[0]
heapq.heapify(lst)
# Max-heap trick: negate values
heapq.heappush(h, -val)

// JavaScript has no built-in heap. Use a class:
class MinHeap {
    constructor() { this.h = []; }
    push(v) {
        this.h.push(v);
        this._up(this.h.length - 1);
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    peek() { return this.h[0]; }
    size() { return this.h.length; }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let s = i;
            if (l < n && this.h[l] < this.h[s]) s = l;
            if (r < n && this.h[r] < this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

The 7 Heap Patterns#

1. Top K Elements#

Use a min-heap of size K. If size exceeds K, pop. Time: O(n log k).

2. Kth Smallest / Kth Largest#

Min-heap for Kth largest, max-heap for Kth smallest. Counter-intuitive but correct.

3. Two Heaps (Median Pattern)#

Max-heap for the lower half, min-heap for the upper half. Median = top of larger heap (or average of both tops).

4. K-Way Merge#

Push the head of each sorted list into a min-heap. Pop, push next from same list. Time: O(n log k).

5. Scheduling and Greedy with Frequency#

Push tasks by remaining count or deadline. Always serve the highest-priority task. Used in Task Scheduler, Reorganize String.

6. Sliding Window with Heap#

Lazy deletion when stale elements are at the top. Simpler than balanced BST when constant factors matter.

7. Min-Heap on Edge Weight#

Dijkstra, Prim, and Furthest Building all use a min-heap for the next-best edge or jump.

Common Mistakes#

• Using max-heap when min-heap is needed (and vice versa) — confuse the polarity.
• Forgetting tie-breakers: Python compares tuples lexicographically, so duplicate priorities crash on non-comparable payloads.
• Pushing the entire array first instead of incremental size-K maintenance.
• Reaching for a heap when sorting once is simpler and cheaper.
• Mutating heap entries in place instead of pushing a new entry and lazy-deleting.

Interview Tips#

• Verbalize: "I want quick access to the min/max while supporting inserts."
• Compute: heapify is O(n), not O(n log n).
• For Kth largest, maintain a min-heap of size K — peek is the answer.
• For streaming medians, balance two heaps within size 1 of each other.
• Mention lazy deletion for heaps with sliding windows.

Follow-up Questions#

• Build a heap in O(n)? Use sift-down from n/2 down to 0.
• Decrease-key in O(log n)? Maintain index map for entries.
• Priority queue with arbitrary comparator in JS? Pass a cmp function to the heap class.
• d-ary heaps? Trade taller depth for shallower fan-out — useful in Dijkstra with dense graphs.

Key Takeaways#

• A heap gives O(log n) push and pop with O(1) peek of the extremum.
• Min-heap of size K solves Kth largest in O(n log k) time and O(k) space.
• Two-heap pattern solves streaming median in O(log n) per insert and O(1) per query.
• K-way merge runs in O(n log k) using a min-heap over k sources.
• Python's heapq is a min-heap; negate values for a max-heap.
• JavaScript has no built-in heap; implement a class or use a library.
• heapify is O(n), not O(n log n) — use it when building from an existing array.