Heap and Priority Queue LeetCode Pattern Guide — Top-K, K-Way Merge, and Median

A heap and priority queue LeetCode pattern guide is really a guide to one question: when do you need the next smallest, next largest, or current best item without sorting everything every time? The pattern shows up in top-K questions, k-way merge, streaming median, task scheduling, meeting rooms, shortest paths, and any interview prompt where the data changes while the answer must stay ordered. The mistake most candidates make is treating a heap as a magic sorting container. A heap is not a sorted array. It is a compact way to keep the most urgent element at the top while updates stay logarithmic.

Heap and priority queue LeetCode pattern guide: when the pattern applies

Reach for a heap when the prompt has one of these signals:

| Signal in the prompt | Heap shape | Why it works | |---|---|---| | "Return the k largest / smallest" | Size-k heap | Avoids sorting all n items | | "Merge k sorted lists / arrays" | Frontier heap | Always expands the smallest current head | | "Find median from data stream" | Two heaps | Keeps lower half and upper half balanced | | "Minimum rooms / machines / intervals" | Min-heap of end times | Tracks earliest resource release | | "Closest points / most frequent" | Size-k heap with custom key | Keeps only the best candidates | | "Repeatedly combine / process smallest" | Min-heap | Simulates the greedy order exactly |

The decision rule is simple: if you only need a small frontier of best candidates, use a heap. If you need every element in complete order once, sorting may be cleaner. If you need membership lookup or arbitrary deletion, a heap alone is not enough; pair it with a map, use lazy deletion, or pick a balanced tree if the language offers one.

The core heap mental model

A binary heap gives you three operations: push, pop top, and peek top. In Python, heapq is a min-heap. In Java, PriorityQueue is also a min-heap unless you pass a comparator. In JavaScript, you usually implement your own heap or use a library if allowed. A max-heap is often simulated by negating numbers or reversing the comparator.

The complexity line candidates should say out loud: heap construction from an array is O(n), each push/pop is O(log n), and peeking is O(1). For top-K, a size-k heap turns O(n log n) sorting into O(n log k). That is the whole point. If k is close to n, the advantage shrinks; if k is tiny, the heap wins clearly.

A heap only guarantees the top element. Iterating through the heap array does not produce sorted order. This is a common bug in explanations and code. If the final output must be sorted, either pop all items into an answer or sort the final k items as a small post-processing step.

Pattern 1: top-K with a size-k heap

The top-K pattern is the most tested heap pattern. The trick is choosing the heap direction based on what you want to eject.

For k largest elements, keep a min-heap of size k. The smallest item among your current winners sits at the top. When a new number is larger than that top, pop the weak winner and push the new one. At the end, the heap contains the k largest, not necessarily sorted.

For k smallest elements, keep a max-heap of size k. In Python that usually means push negative values, or push tuples with negated keys. The largest item among your current winners sits at the top, ready to be ejected.

The interview explanation:

1. I do not need all elements sorted.
2. I only need to preserve the best k seen so far.
3. The boundary candidate is the top of a heap with size k.
4. Each new item either fails the boundary or replaces it.
5. The total cost is O(n log k) and space is O(k).

For "top k frequent elements," first count frequencies with a hash map, then heap the (frequency, value) pairs. Do not push every occurrence into the heap. The heap should operate on unique values, not raw input positions, otherwise you turn a clean O(n + m log k) solution into a noisy one.

Pattern 2: k-way merge

K-way merge appears as merge k sorted lists, find the kth smallest in sorted matrix, employee free time, and smallest range covering k lists. The pattern is to put one candidate from each sorted source into a min-heap. Pop the smallest candidate, append or evaluate it, then push the next item from the same source.

The heap entry must carry enough metadata to advance the source:

| Problem | Heap entry usually contains | |---|---| | K sorted linked lists | value, list index or node reference | | K sorted arrays | value, array index, element index | | Sorted matrix | value, row, column | | Smallest range | value, list id, index in list |

The power of the pattern is that the heap size is k, not n. If there are n total items across all lists, the merge costs O(n log k) and uses O(k) extra space.

The trap is duplicate pushing. In a matrix, pushing right and down from every popped cell can create duplicate visits unless you track visited coordinates. If each row is sorted and you push only the next column in the same row, you do not need a visited set. The cleaner approach depends on the matrix constraints. Say why your frontier cannot duplicate cells.

For linked lists, include a tie-breaker in languages where heap entries compare the whole tuple. In Python, (node.val, node) can fail when values tie because nodes are not orderable. Use (node.val, counter, node) or (node.val, list_id, node).

Pattern 3: median from a data stream

The median stream problem is a heap fluency test. Use two heaps:

• low: max-heap for the lower half
• high: min-heap for the upper half

Maintain two invariants. First, every value in low is less than or equal to every value in high. Second, the heaps are balanced so their sizes differ by at most one. Then the median is immediate: if one heap is larger, its top is the median; if equal size, average both tops.

A clean insertion plan:

1. Push into low if the value belongs in the lower half; otherwise push into high.
2. If low is too large, move its top to high.
3. If high is too large, move its top to low.
4. Read median from the heap tops.

The common bug is balancing sizes but not ordering. If low accidentally contains a value larger than high.top, the median is wrong even if sizes look perfect. After insertion, compare tops or insert through one heap and transfer to the other to preserve the boundary.

This pattern also extends to sliding window median, but that version needs lazy deletion because heaps do not support efficient removal of an arbitrary outgoing element. A hash map of delayed deletions plus a prune function is the standard advanced solution.

Pattern 4: scheduling, intervals, and resource allocation

When a problem asks for minimum meeting rooms, CPU intervals, car pooling, or smallest number of machines, the heap usually tracks the next resource to become available. Sort by start time, then keep a min-heap of end times.

For meeting rooms:

1. Sort intervals by start.
2. For each interval, pop all rooms whose end time is less than or equal to the current start if reuse is allowed.
3. Push the current end time.
4. The maximum heap size is the rooms required.

The boundary condition matters. If a meeting ends at 10 and another starts at 10, most versions allow reuse, so use end <= start. If the problem says inclusive intervals, use end < start. This one comparison can flip accepted to wrong answer.

For task scheduler with cooldown, the heap tracks remaining counts while a queue tracks cooldown release time. A heap alone cannot enforce cooling; a queue alone cannot choose the most frequent available task. The pattern is heap plus time simulation.

Choosing min-heap vs max-heap

Ask: which candidate do I need to remove quickly?

| Goal | Heap to keep | Top represents | |---|---|---| | K largest | Min-heap of size k | Weakest winner | | K smallest | Max-heap of size k | Weakest winner | | Merge sorted sources | Min-heap | Next global smallest | | Median lower half | Max-heap | Largest lower value | | Median upper half | Min-heap | Smallest upper value | | Earliest available room | Min-heap | Earliest ending resource | | Most frequent next task | Max-heap | Highest remaining count |

If you can explain the top as "the boundary" or "the next item to process," you probably chose the right heap.

Common traps interviewers are watching for

Sorting when k is small. Sorting is often accepted for easy versions, but it misses the intended optimization. Mention the sort baseline, then improve it.

Heap entries without metadata. A value alone is not enough for k-way merge; you need to know where to advance next.

Forgetting final order. A heap containing the top k items is not sorted. If the answer requires descending order, sort or pop after collection.

Wrong tie behavior. Custom comparators must be deterministic. Tie by value, index, or insertion counter as needed.

Negation confusion. In Python max-heap simulation, remember to negate when pushing and when reading. Many median bugs are just forgotten sign conversions.

Deleting arbitrary items. Standard heaps do not remove arbitrary stale values efficiently. Sliding window variants need lazy deletion.

Using heap when a deque is better. Monotonic queue problems like sliding window maximum are not heap-first if you need exact window expiration and linear time. A heap can work with lazy deletion at O(n log n), but deque is optimal.

Prep checklist for heap problems

Before coding, answer these questions on the whiteboard:

• What does the heap top represent?
• What is the maximum heap size?
• Is the heap min-oriented or max-oriented?
• Do heap entries need index, source id, count, or node reference?
• Can stale entries occur? If yes, how are they removed?
• Does the final answer need sorted output?
• What happens on ties?
• What is the exact push/pop count?

Then code the heap helpers first if your language needs them. In JavaScript, a bug in heap implementation can sink the whole problem, so keep a memorized push, pop, siftUp, and siftDown template. In Python or Java, spend the time on entry shape and comparator correctness.

How to talk about heaps in interviews and resumes

In an interview, do not say "I will use a priority queue" and immediately code. Say the invariant. For top-K: "I maintain a min-heap of the best k values seen so far; the top is the smallest accepted value, so any smaller new value can be discarded." For median: "I maintain two heaps split around the median, with size balance and ordering invariants." For k-way merge: "The heap is the frontier across sorted sources. Each pop advances exactly one source."

On a resume, translate the pattern into system impact instead of naming LeetCode. Good phrasing: "Implemented priority-queue scheduler that selected the highest-value pending job under resource constraints, reducing manual prioritization work." Or: "Built streaming percentile calculation using bounded heaps to avoid full-data resorting." The signal is not that you know a heap; it is that you can maintain an ordered frontier while data changes.

A strong heap answer sounds calm because the invariant is clear. Define the heap top, define what gets pushed next, protect the boundary cases, and the code becomes much smaller than the problem statement looks.

Related guides

• Divide and Conquer LeetCode Pattern Guide — Merge Sort, Quickselect, and Recursion — A practical LeetCode pattern guide for divide and conquer: master recursive contracts, merge sort variations, quickselect, tree recursion, complexity, and common interview traps.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.
• BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.
• Binary Search LeetCode Pattern Guide — Bounds, Rotated Arrays, and Search-on-Answer — A binary search LeetCode pattern guide for exact search, lower/upper bounds, rotated arrays, and search-on-answer problems. Includes invariants, templates, traps, and interview-ready explanations.
• Bit Manipulation LeetCode Pattern Guide — XOR Tricks, Masks, and Counting Bits — A practical bit manipulation LeetCode pattern guide covering XOR tricks, masks, counting bits, subset enumeration, flags, and the interview pitfalls around signed integers.