Heap

A heap is a complete binary tree stored as an array that gives O(log n) insertion and O(1) peek of the minimum (or maximum) — Java's PriorityQueue is a min-heap by default.

• Replaces O(n) repeated linear scans with O(log n) insertions and O(1) peek — critical when you need the extreme element repeatedly as data arrives
• Two variants: min-heap (smallest at top, default) and max-heap (largest at top, use (a, b) -> b - a comparator)
• Reach for it when the problem asks for the kth element, the top-k items, merging sorted sequences, or tracking a running median

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of heap patterns.

Practice Tips

How to Identify a Heap Problem

• Problem asks for kth largest, kth smallest, or top k by some criterion
• You need to repeatedly access the minimum or maximum as new elements arrive
• Multiple sorted sequences need to be merged (k-way merge)
• Intervals: need to track the "earliest finishing" event at each step
• Running calculation (median, rank) on a stream of incoming numbers

Heap vs. Other Techniques

Interview Approach

1. Identify which heap pattern: bounded size-k heap, k-way merge, two-heap, or interval scheduling
2. Choose heap direction: min-heap keeps k largest (evict minimum); max-heap keeps k smallest (evict maximum)
3. Write the comparator explicitly — (a, b) -> a - b is min, (a, b) -> b - a is max
4. For custom objects (arrays, nodes), comparator accesses the right field: (a, b) -> a[0] - b[0]
5. Always check heap.isEmpty() before peek() or poll()

4 Main Patterns

Pattern 1: Bounded Heap (Top K)

Copy// Min-heap of size k keeps the k LARGEST elements (evict the smallest)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) {
        minHeap.poll();  // evict smallest
    }
}
// minHeap.peek() = kth largest

// Max-heap of size k keeps the k SMALLEST elements (evict the largest)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
for (int num : nums) {
    maxHeap.offer(num);
    if (maxHeap.size() > k) {
        maxHeap.poll();  // evict largest
    }
}
// maxHeap.peek() = kth smallest

Pattern 2: K-way Merge

Copy// Heap holds one element per source; always extract the global min
// [value, source_index, position_in_source]
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
// seed: add first element of each source
while (!heap.isEmpty()) {
    int[] curr = heap.poll();          // global minimum
    // add next element from the same source
    if (hasNext(curr)) {
        heap.offer(next(curr));
    }
}

Pattern 3: Two-Heap for Median

Copy// small = max-heap (lower half), large = min-heap (upper half)
// Invariant: small.size() == large.size() or small.size() == large.size() + 1
PriorityQueue<Integer> small = new PriorityQueue<>((a, b) -> b - a); // max-heap
PriorityQueue<Integer> large = new PriorityQueue<>();                  // min-heap
// addNum: always add to small first, then cross-check, then rebalance
small.offer(num);
large.offer(small.poll());              // ensure small's max <= large's min
if (small.size() < large.size()) {
    small.offer(large.poll()); // rebalance
}

Pattern 4: Interval Scheduling

Copy// Sort by start time; heap tracks end times of active/assigned intervals
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> heap = new PriorityQueue<>();  // min-heap of end times
for (int[] interval : intervals) {
    if (!heap.isEmpty() && heap.peek() <= interval[0]) {
        heap.poll();                    // reuse: earliest-ending is now free
    }
    heap.offer(interval[1]);           // assign this interval
}
// heap.size() = number of rooms/workers/resources needed

General Templates

Java PriorityQueue Quick Reference

Copy// Min-heap (default — smallest element at top)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-heap (largest element at top)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

// Custom: sort int[] by first element ascending
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

heap.offer(x);   // insert — O(log n)
heap.poll();     // remove and return top — O(log n)
heap.peek();     // view top without removing — O(1)
heap.size();     // number of elements — O(1)

Problem 1: Kth Largest Element in an Array ⭐ MUST DO

Find the kth largest element in an unsorted array.

Example:

CopyInput:  nums = [3,2,1,5,6,4],  k = 2  →  5
Input:  nums = [3,2,3,1,2,4,5,5,6],  k = 4  →  4

Key Insight:

• Use a min-heap of size k (counterintuitive: min not max). It holds the k largest elements seen so far. The heap's minimum is the kth largest — anything smaller than the heap's minimum cannot be in the top k, so evict it. After the loop, peek is the answer.

Solution:

Copypublic int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();  // evict smallest
        }
    }
    return minHeap.peek();                       // kth largest
}

Complexity:

Real World: Recommendation engines rank items by a score (click-through rate, rating, relevance) and only need the top k results — not a full sort. A size-k min-heap processes the full catalogue in O(n log k) and keeps memory bounded at k regardless of catalogue size. Same pattern in log analysis: find the k slowest requests from millions of log lines.

Variations:

1. Kth largest in a stream — same heap but elements arrive one at a time; maintain the heap as a running state rather than processing a full array at once.
2. Kth smallest — flip to a max-heap of size k; evict the largest so the k smallest remain.

Interview Disguises:

• "Given a list of server response times, find the 99th percentile latency without sorting the full list." — kth largest where k = 1% of n; min-heap of size k.
• "A leaderboard receives score updates continuously. At any point return the top 10 players." — bounded min-heap of size 10 maintained as a running state; same as kth largest in a stream.

Problem 2: Top K Frequent Elements ⭐ MUST DO [B75-347]

Return the k most frequent elements from an integer array.

Example:

CopyInput:  nums = [1,1,1,2,2,3],  k = 2  →  [1,2]
Input:  nums = [1],             k = 1  →  [1]

Key Insight:

• Same bounded min-heap pattern as Kth Largest, but the comparison key is frequency, not value. Count frequencies in a HashMap, then apply the size-k min-heap with a comparator that compares by count.get(a). The k most frequent remain in the heap.

Solution:

Copypublic int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.put(num, count.getOrDefault(num, 0) + 1);
    }

    PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> count.get(a) - count.get(b));
    for (int num : count.keySet()) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }

    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

Complexity:

Real World: Analytics dashboards showing "top k trending hashtags" or "most visited pages" over a rolling time window. The frequency map is updated as events arrive; rebuilding the top-k heap periodically is O(d log k) not O(d log d). Same pattern in autocomplete: surface the k most frequently typed completions for a given prefix.

Variations:

1. Top k by custom weight — replace the frequency comparator with any scoring function (recency-weighted count, TF-IDF score). The heap structure doesn't change, only the comparator.
2. Bucket sort O(n) solution — create n+1 frequency buckets, place each element in its bucket, then scan from the highest bucket down until k elements are collected. O(n) time, O(n) space — beats the heap when k is close to n.

Interview Disguises:

• "Given server access logs, return the k most accessed API endpoints in the last hour." — frequency count by endpoint, then top-k min-heap by count.
• "Find the k words that appear most often in a document corpus. Memory is limited so you cannot sort all words." — top k frequent with bounded heap; O(n log k) and O(k) working memory.

Problem 3: K Closest Points to Origin

Return the k closest points to the origin (0, 0).

Example:

CopyInput:  points = [[1,3],[-2,2]],  k = 1  →  [[-2,2]]
Input:  points = [[3,3],[5,-1],[-2,4]],  k = 2  →  [[3,3],[-2,4]]

Key Insight:

• To keep the k smallest distances, use a max-heap of size k and evict the farthest. No need to compute sqrt — comparing squared Euclidean distances is equivalent and avoids floating point. When heap.size() > k, poll removes the farthest point (max-heap top).

Solution:

Copypublic int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
        (a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1])
    );
    for (int[] point : points) {
        maxHeap.offer(point);
        if (maxHeap.size() > k) {
            maxHeap.poll();  // evict farthest
        }
    }
    int[][] result = new int[k][2];
    for (int i = 0; i < k; i++) {
        result[i] = maxHeap.poll();
    }
    return result;
}

Complexity:

Real World: Ride-sharing dispatch: given GPS coordinates of all available drivers, find the k nearest to a pickup request. Squared Euclidean distance avoids the sqrt and gives the same ordering. Also used in k-nearest-neighbour classification and spatial indexing when a full sort of all points is too slow.

Variations:

1. K closest by Manhattan distance — replace the Euclidean distance formula with |x| + |y|; same max-heap structure, different comparator.
2. Closest point to a query point (not origin) — shift coordinates: replace a[0]*a[0] + a[1]*a[1] with (a[0]-qx)*(a[0]-qx) + (a[1]-qy)*(a[1]-qy).

Interview Disguises:

• "Given a list of warehouses with coordinates, return the k closest to a distribution centre." — k closest points where the centre is the query point, not the origin.
• "A food delivery app needs to show the k nearest restaurants to a user's location." — same problem; use squared distance to avoid floating point; max-heap of size k.

Problem 4: Meeting Rooms II ⭐ MUST DO

Given a list of meeting intervals [start, end], return the minimum number of conference rooms required.

Example:

CopyInput:  [[0,30],[5,10],[15,20]]  →  2
Input:  [[7,10],[2,4]]           →  1

Key Insight:

• Sort meetings by start time. Use a min-heap of end times — one entry per room currently in use. For each new meeting, if the earliest-ending meeting has already finished (heap.peek() <= start), that room is free: remove it and reuse it. Always add the new meeting's end time. The heap size after processing all meetings is the answer.

Solution:

Copypublic int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> endTimes = new PriorityQueue<>();
    for (int[] meeting : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= meeting[0]) {
            endTimes.poll();            // reuse room: earliest meeting just ended
        }
        endTimes.offer(meeting[1]);     // assign room, track end time
    }
    return endTimes.size();
}

Complexity:

Real World: Any resource allocation problem where jobs arrive with a start and end time and you need the minimum number of workers, threads, or servers: CI/CD pipeline job scheduling, cloud VM slot allocation, hospital bed assignment. The heap models resources currently in use; its size at any point is the current demand.

Variations:

1. Maximum overlap at any instant — same algorithm; the answer is the peak heap size during the sweep, which equals the minimum rooms needed.
2. Assign meetings to specific rooms — track which room (ID) is in the heap alongside its end time; on reuse, record the room assignment. Same heap, richer payload.

Interview Disguises:

• "Given a list of flight intervals, find the minimum number of airport gates required so no two flights share a gate simultaneously." — meeting rooms II with flights as intervals.
• "A streaming platform starts and stops video encodes. Find the peak number of concurrent encodes to size the worker pool." — same problem; intervals are encode start/end times.

Problem 5: Kth Smallest Element in a Sorted Matrix

Find the kth smallest element in an n×n matrix where each row and column is sorted in ascending order.

Example:

CopyInput:  matrix = [[1,5,9],[10,11,13],[12,13,15]],  k = 8  →  13
Input:  matrix = [[-5]],  k = 1  →  -5

Key Insight:

• Treat each row as a sorted list. Start the min-heap with the first element of each row (up to k rows). On each extraction, add the next element from the same row. After k extractions, the last extracted value is the answer — same as Merge K Sorted Lists.

Solution:

Copypublic int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    for (int i = 0; i < Math.min(n, k); i++) {
        minHeap.offer(new int[]{matrix[i][0], i, 0});  // [value, row, col]
    }

    int val = 0;
    for (int i = 0; i < k; i++) {
        int[] curr = minHeap.poll();
        val = curr[0];
        int row = curr[1], col = curr[2];
        if (col + 1 < n) {
            minHeap.offer(new int[]{matrix[row][col + 1], row, col + 1});
        }
    }
    return val;
}

Complexity:

Real World: Database query planners that merge results from multiple sorted index scans — each scan is a sorted sequence, the heap picks the globally smallest row at each step. Also used in external merge sort: when merging k sorted file chunks that don't fit in memory, a k-way heap merge reads the minimum across all chunks without loading them fully.

Variations:

1. Kth smallest in k sorted arrays — same pattern; seed with the first element of each array, advance within the same array on each poll.
2. Find the median of a sorted matrix — binary search on value combined with a count of elements ≤ mid; or k-way merge up to the n²/2 th element.

Interview Disguises:

• "You have k database shards each returning sorted result pages. Merge them into a single sorted stream without loading all results into memory." — k-way merge; heap holds the current front of each shard's page.
• "Given a sorted matrix, find the kth smallest sum of any row pair (one element from each row)." — variant; heap tracks candidate sums with indices to generate next candidates.

Problem 6: Task Scheduler

Given a list of tasks and a cooldown period n, return the minimum time to execute all tasks. Identical tasks must be separated by at least n intervals.

Example:

CopyInput:  tasks = ["A","A","A","B","B","B"],  n = 2  →  8   (A→B→idle→A→B→idle→A→B)
Input:  tasks = ["A","A","A","B","B","B"],  n = 0  →  6

Key Insight:

• Greedy: always execute the most frequent remaining task first. In each cooldown cycle of n+1 time slots, execute up to n+1 distinct tasks (most frequent first), then add idle slots if fewer than n+1 distinct tasks remain. Repeat until all tasks are done.

Solution:

Copypublic int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char task : tasks) {
        freq[task - 'A']++;
    }

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
    for (int f : freq) {
        if (f > 0) maxHeap.offer(f);
    }

    int time = 0;
    while (!maxHeap.isEmpty()) {
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i <= n; i++) {           // one cooldown cycle: n+1 slots
            if (!maxHeap.isEmpty()) {
                int f = maxHeap.poll();
                if (f > 1) {
                    temp.add(f - 1);
                }
            }
            time++;
            if (maxHeap.isEmpty() && temp.isEmpty()) {
                break; // no more tasks
            }
        }
        for (int f : temp) {
            maxHeap.offer(f);
        }
    }
    return time;
}

Complexity:

Real World: OS CPU schedulers balance task fairness with throughput — a cooldown prevents the same process from monopolising the CPU. The "most frequent first" greedy minimises total time, which maps to minimising context switches. Also appears in rate-limited API call scheduling: if the same endpoint can only be called once every n seconds, schedule the most-needed calls first.

Variations:

1. Math formula O(1) — the answer is max(totalTasks, (maxFreq - 1) * (n + 1) + countOfMaxFreq). The heap solution is easier to derive under pressure; the formula is the follow-up once the greedy logic is clear.
2. Tasks with dependencies — if task B must run after task A, this becomes a topological sort problem (see Graphs). The cooldown constraint alone is handled by the heap approach.

Interview Disguises:

• "A rate limiter allows each API endpoint to be called at most once every n seconds. Given a sequence of requests, find the minimum total time to process all of them." — task scheduler with endpoints as task types and n as the cooldown.
• "A print queue has jobs of k types. Each printer needs a cooldown of n jobs between same-type prints. Minimise total print time." — identical structure; job types map to task characters.

Problem 7: Merge K Sorted Lists ⭐ MUST DO [B75-23]

Merge k sorted linked lists into one sorted list.

Example:

CopyInput:  [[1,4,5],[1,3,4],[2,6]]  →  [1,1,2,3,4,4,5,6]

Key Insight:

• Seed the min-heap with the first node of each non-null list. Always extract the global minimum, append it to the result, then add its next node (if any) back to the heap. At most k nodes are in the heap at any time.

Solution:

Copypublic ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode node : lists) {
        if (node != null) minHeap.offer(node);
    }

    ListNode dummy = new ListNode(0), curr = dummy;
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        curr.next = node;
        curr = curr.next;
        if (node.next != null) {
            minHeap.offer(node.next);
        }
    }
    return dummy.next;
}

Complexity:

Real World: Distributed databases merge sorted results from k shards into a single sorted response — each shard returns a sorted page and the coordinator uses a k-way heap merge. Also the final step of external merge sort: k sorted temporary files are merged into one output file by always writing the smallest available record.

Variations:

1. Merge k sorted arrays — same algorithm; store [value, arrayIndex, elementIndex] in the heap instead of list nodes.
2. Find the smallest range covering at least one element from each list — extend k-way merge: track the current max across all heap entries alongside the min (heap top); the range is [min, max]; advance the list containing the current min and update max.

Interview Disguises:

• "You have k microservices each producing a sorted stream of timestamped events. Merge them into a single chronological stream." — merge k sorted lists where nodes are events sorted by timestamp.
• "Given k sorted log files, produce a single merged log sorted by timestamp for ingestion into a data warehouse." — same structure; each file is a sorted list, heap picks the earliest timestamp at each step.

Problem 8: Find Median from Data Stream ⭐ MUST DO [B75-295]

Design a data structure that supports adding integers and finding the median at any time.

Example:

CopyaddNum(1) → addNum(2) → findMedian() → 1.5
addNum(3) → findMedian() → 2.0

Key Insight:

• Maintain two heaps: small (max-heap) holds the lower half, large (min-heap) holds the upper half. Invariant: small.size() == large.size() (even count, median = average of tops) or small.size() == large.size() + 1 (odd count, median = small.peek()).
• Add to small first, then move small's max to large to ensure the split is valid, then rebalance if large grew larger than small.

Solution:

Copyclass MedianFinder {
    private PriorityQueue<Integer> small; // max-heap: lower half
    private PriorityQueue<Integer> large; // min-heap: upper half

    public MedianFinder() {
        small = new PriorityQueue<>((a, b) -> b - a);
        large = new PriorityQueue<>();
    }

    public void addNum(int num) {
        small.offer(num);
        large.offer(small.poll());              // ensure small's max ≤ large's min
        if (small.size() < large.size()) {
            small.offer(large.poll());          // rebalance: small must be >= large
        }
    }

    public double findMedian() {
        return small.size() > large.size()
            ? small.peek()
            : (small.peek() + large.peek()) / 2.0;
    }
}

Complexity:

Real World: Real-time analytics systems that report the median latency or median transaction value over a sliding window of incoming events — you can't sort a live stream, so the two-heap invariant gives O(1) median at any instant. Used in monitoring dashboards, fraud detection score tracking, and A/B test metric aggregation where the median is more robust than the mean.

Variations:

1. Sliding window median — same two-heap structure but elements also leave the window; requires a lazy deletion map to mark removed elements and skip them on poll. Significantly harder — a common hard follow-up.
2. Kth percentile instead of median — adjust the size invariant: instead of keeping the heaps balanced at 50/50, maintain small.size() = k% of total and large.size() = (100-k)% of total. The kth percentile is always small.peek().

Interview Disguises:

• "A trading system receives a stream of stock prices. After each price, report the median price seen so far to detect if the market is drifting." — find median from data stream; each tick is an addNum call.
• "Monitor API response times in real time. At any moment, return the median response time without storing the full history sorted." — same structure; each response time is a data point added to the two-heap.

Quick Reference Table

When to Use Each Pattern

Bounded Heap (Top K)

• "Return the k largest/smallest/most frequent/closest" — fixed k, process all n elements
• Min-heap of size k keeps k largest; max-heap of size k keeps k smallest
• After the loop, drain the heap into the result array

K-way Merge

• Multiple sorted sequences (lists, arrays, matrix rows) need to be merged
• Seed heap with the first element of each source (with source pointer)
• On each poll, add the next element from that same source
• Stops when heap is empty (all sources exhausted)

Two-Heap for Median

• Running median on a stream — need O(1) access to both halves of the data
• small (max-heap) = lower half, large (min-heap) = upper half
• Invariant: small.size() ≥ large.size() and small.peek() ≤ large.peek()
• Median = small.peek() if sizes differ, else average of both tops

Interval Scheduling

• Sort intervals by start time; need to match "available" resources to new intervals
• Min-heap of end times tracks when each resource next becomes free
• On each new interval: if heap.peek() <= start, reclaim that resource (poll), then push new end time
• Final heap size = number of resources (rooms, workers) required

Common Mistakes to Avoid

General Heap Mistakes

1. Wrong heap direction for top-k — to keep k largest, use a MIN-heap (not max): you evict the smallest of the k+1 candidates; similarly, to keep k smallest, use a MAX-heap
2. Not copying result from heap — drain the heap at the end with poll(), not peek(); peek() only reads the top
3. Integer overflow in comparator — (a, b) -> b - a overflows when values span the full int range; use Integer.compare(b, a) if values could be near Integer.MIN_VALUE

Bounded Heap Mistakes

4. Calling peek on empty heap — always check !heap.isEmpty() before calling peek() or poll(); PriorityQueue throws NoSuchElementException on empty peek/poll

Two-Heap Mistakes

5. Wrong rebalance condition — small must never be smaller than large; the condition is if (small.size() < large.size()) small.offer(large.poll()); reversing this breaks the median formula
6. Skipping the cross-check on add — adding to small and immediately rebalancing without moving small's max to large first can violate the invariant that small.peek() ≤ large.peek()

K-way Merge Mistakes

7. Not seeding null-safe — check if (node != null) before adding to the heap; null list heads cause NullPointerException in the comparator
8. Forgetting to advance the pointer — after polling a node, add node.next (not a fresh reference) back to the heap; each extracted node must be followed by its successor or nothing