Top K Frequent Elements Using Heap in DSA Javascript

Mental Model

We want to find the k numbers that appear most often in a list by counting frequencies and using a small structure to keep track of the top counts.

Analogy: Imagine you have a bag of colored balls and want to find the k colors you have the most of. You count how many balls of each color you have, then keep only the top k colors in a small box that always removes the least frequent color when a new more frequent one comes in.

Input array: [1, 1, 1, 2, 2, 3]
Frequency map: {1:3, 2:2, 3:1}
Min-heap (size k=2):
  [ (2,2), (1,3) ]  ← keeps top 2 frequent elements
Heap root points to smallest frequency

Dry Run Walkthrough

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

Goal: Find the 2 numbers that appear most frequently in nums

Step 1: Count frequency of each number

Frequency map: {1:3, 2:2, 3:1}

Why: We need to know how often each number appears to find the most frequent ones

Step 2: Add (1,3) to min-heap

Heap: [(1,3)]

Why: Start building heap with first frequency

Step 3: Add (2,2) to min-heap

Heap: [(2,2), (1,3)]  (2,2) is root because 2 < 3)

Why: Keep heap size ≤ k=2, root is smallest frequency

Step 4: Add (3,1) to min-heap, but frequency 1 < root frequency 2, so ignore

Heap unchanged: [(2,2), (1,3)]

Why: We only keep top k frequencies, so ignore smaller frequency

Result:

Heap contains [(2,2), (1,3)] -> top 2 frequent elements are 1 and 2

Annotated Code

DSA Javascript

class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

  peek() {
    return this.heap[0];
  }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex][1] <= this.heap[index][1]) break;
      this.swap(parentIndex, index);
      index = parentIndex;
    }
  }

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return root;
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      if (left < length && this.heap[left][1] < this.heap[smallest][1]) {
        smallest = left;
      }
      if (right < length && this.heap[right][1] < this.heap[smallest][1]) {
        smallest = right;
      }
      if (smallest === index) break;
      this.swap(index, smallest);
      index = smallest;
    }
  }
}

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

  const minHeap = new MinHeap();
  for (const [num, freq] of freqMap.entries()) {
    if (minHeap.size() < k) {
      minHeap.push([num, freq]);
    } else if (freq > minHeap.peek()[1]) {
      minHeap.pop();
      minHeap.push([num, freq]);
    }
  }

  const result = [];
  while (minHeap.size() > 0) {
    result.push(minHeap.pop()[0]);
  }
  return result.reverse();
}

// Driver code
const nums = [1,1,1,2,2,3];
const k = 2;
console.log(topKFrequent(nums, k).join(' -> ') + ' -> null');

for (const num of nums) { freqMap.set(num, (freqMap.get(num) || 0) + 1); }

Count frequency of each number in nums

if (minHeap.size() < k) { minHeap.push([num, freq]); }

Add element to heap if heap size less than k

else if (freq > minHeap.peek()[1]) { minHeap.pop(); minHeap.push([num, freq]); }

Replace root if current frequency is higher to keep top k frequent

while (minHeap.size() > 0) { result.push(minHeap.pop()[0]); }

Extract elements from heap to build result

Output

1 -> 2 -> null

Complexity Analysis

Time: O(n log k) because we count frequencies in O(n) and maintain a heap of size k for n unique elements, each insertion/removal costs O(log k)

Space: O(n) for frequency map and O(k) for heap, total O(n) in worst case

vs Alternative: Using sorting on all frequencies costs O(n log n), heap reduces this to O(n log k) which is faster when k << n

Edge Cases

Empty input array

Returns empty list since no elements to count

DSA Javascript

for (const num of nums) { freqMap.set(num, (freqMap.get(num) || 0) + 1); }

k equals number of unique elements

Returns all unique elements sorted by frequency

DSA Javascript

if (minHeap.size() < k) { minHeap.push([num, freq]); }

All elements have same frequency

Returns any k elements since frequencies tie

DSA Javascript

else if (freq > minHeap.peek()[1]) { minHeap.pop(); minHeap.push([num, freq]); }

When to Use This Pattern

When asked to find the top k frequent items efficiently, use a heap to keep track of the k largest frequencies without sorting all elements.

Common Mistakes

Mistake: Using a max-heap and extracting all elements then slicing top k, which is less efficient
Fix: Use a min-heap of size k to keep only top k elements during iteration

Summary

Finds the k most frequent elements in a list using a frequency map and a min-heap.

Use when you need the top k frequent items efficiently without sorting all elements.

Keep a min-heap of size k to track top frequencies, replacing the smallest when a bigger frequency appears.