Heap / Priority Queue Pattern

Why this pattern matters for LeetCode

When a problem asks for the k largest elements, the brute force sorts everything — O(n log n). A heap of size k does it in O(n log k) by keeping only k elements in memory at once. The difference is meaningful when k is small: k = 10 and n = 1,000,000 means 20 operations per element instead of 20,000,000. More importantly, heaps handle streaming data where elements arrive one at a time and you can't sort in advance — you need to maintain the top k after each new arrival.

What the Heap / Priority Queue pattern is

A heap (priority queue) always gives you the minimum (min-heap) or maximum (max-heap) element in O(1), with insertions and deletions in O(log n). For 'top k largest' problems, maintain a min-heap of size k: push each element, and if the heap exceeds k, pop the minimum. What remains is the k largest elements — the root is the kth largest. JavaScript has no built-in heap; on LeetCode, a sort-based approach is common, but understanding the heap trade-off matters when inputs are large or data arrives incrementally.

Reach for Heap / Priority Queue when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Heap / Priority Queue

• ✓Finding the k largest or k smallest elements from an array or stream
• ✓Finding the kth largest or kth smallest element overall
• ✓Merging k sorted lists — always pop the minimum from the current fronts, push the next from the same list
• ✓Scheduling tasks by priority — always process the highest-priority item next
• ✓Finding the running median — two heaps: a max-heap for the lower half and a min-heap for the upper half

When NOT to use Heap / Priority Queue

• ✕You only need the single global maximum or minimum — a one-pass loop is faster and simpler
• ✕k equals n — sorting the whole array is equivalent and simpler to write
• ✕The input is already sorted — index directly into it, no heap needed
• ✕You need all elements in sorted order — sort the array; a heap gives you sorted extraction but at the same O(n log n) cost

Better alternative: In those cases, a simple loop (for global max/min) or Array.sort() (when k equals n or you need full ordering) is more readable and sufficient.

JavaScript code template

Top K Frequent Elements — O(n log k) conceptually; sort-based in JS

function topKFrequent(nums, k) {
  const freq = new Map();
  for (const num of nums) {
    freq.set(num, (freq.get(num) ?? 0) + 1);
  }

  // JS has no built-in heap — sort all entries by frequency descending.
  // A min-heap of size k would give O(n log k) instead of O(n log n):
  //   push each entry, pop the minimum whenever size exceeds k.
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([val]) => val);
}

Build the frequency map in one O(n) pass. Then find the top k by frequency. With a min-heap of size k, you'd push each (value, frequency) pair and pop the minimum whenever the heap exceeds k — leaving exactly the k most frequent without sorting all entries. The heap approach is O(n log k); sorting is O(n log n). In JavaScript, sort is the practical substitute — accepted on LeetCode within typical constraints. The heap trade-off matters when n is large and k is small.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Ask: do I need the k largest, k smallest, or kth element? That's the heap signal.
2. 2Choose min-heap for 'k largest' (keep k largest by ejecting the smallest) or max-heap for 'k smallest.'
3. 3Push each element into the heap. After each push, if size exceeds k, pop the root.
4. 4After processing all elements, the heap holds exactly the k elements you need.
5. 5The heap's root (smallest of the k largest, or largest of the k smallest) is the kth element.
6. 6In JavaScript, substitute with sort() + slice() when a heap library isn't available.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Top K Frequent Elements

  Build a frequency map, then use a heap (or sort) to extract the k most frequent elements.

  Premium→

Coming soon

• Kth Largest Element in an Array

  Maintain a min-heap of size k. After processing all elements, the root is the kth largest.

  Coming soon
• K Closest Points to Origin

  Compute each point's squared distance, then use a max-heap of size k — eject the farthest whenever the heap exceeds k.

  Coming soon
• Find Median from Data Stream

  Two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep their sizes balanced to read the median in O(1).

  Coming soon
• Task Scheduler

  Always execute the most frequent remaining task next — use a max-heap to pick it in O(log n) after each cycle.

  Coming soon

Common mistakes beginners make

• ✕Using a max-heap when you need a min-heap for 'top k largest' — you want to eject the smallest to keep the largest, so you need a min-heap of size k.
• ✕Sorting the entire array when k is small — O(n log n) vs O(n log k) is a real difference at scale, and it misses the heap's main use case.
• ✕Confusing 'kth largest' (one specific element) with 'k largest' (a set of k elements) — a heap gives you both, but the question determines what you return.
• ✕Forgetting that JavaScript has no built-in heap — clarify whether the sort-based substitute is acceptable before committing to it on a time-constrained problem.

Heap vs Sort vs Monotonic Stack

Choose the right tool for the job.

Time and space complexity

Pushing n elements into a heap of size k costs O(log k) per push — O(n log k) total. The heap holds at most k elements, so space is O(k). Building a heap over all n elements (without the size-k cap) costs O(n) via heapify or O(n log n) via repeated insertion, with O(n) space.

Frequently asked questions

When do I use a min-heap vs a max-heap?

For 'k largest,' use a min-heap of size k — the smallest of the k largest is what you eject when something bigger arrives, and the root is the kth largest overall. For 'k smallest,' use a max-heap of size k — the largest of the k smallest is ejected when something smaller arrives. The heap type is always the opposite of what you're keeping.

Why does JavaScript not have a built-in heap?

JavaScript's standard library focuses on web APIs and general-purpose utilities rather than data structure primitives. For LeetCode problems with typical constraints, the sort-based substitute is almost always accepted within time limits. In production code, libraries like @datastructures-js/priority-queue provide a proper heap implementation.

How is a heap different from keeping a sorted array?

Both give you access to the min or max. But inserting into a sorted array requires shifting elements — O(n) per insert. A heap insert is O(log n). For repeated insertions and deletions, the heap is much faster. For a static collection you query once, sorting is simpler. Use a heap when the set is dynamic.

What does 'heapify' mean and why is it O(n)?

Heapify converts an unsorted array into a valid heap in O(n) — faster than inserting each element one by one (which would be O(n log n)). The O(n) bound comes from the fact that most elements are near the bottom of the heap where sift-down operations are cheap. JavaScript's sort is O(n log n) and doesn't give you the incremental insert/delete operations that make heaps useful for streaming data.