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.

Practice

1. What is the main purpose of using a heap in the Top K Frequent Elements problem?

easy

A. To store elements without any order

B. To sort all elements in ascending order

C. To remove duplicates from the list

D. To efficiently keep track of the top K elements by frequency

Solution

1. Step 1: Understand the problem goal

   The goal is to find the K elements that appear most frequently in a list.

2. Step 2: Role of heap in this context

   A heap helps keep track of the top K frequent elements efficiently by always having the smallest frequency at the root, so less frequent elements can be removed quickly.

3. Final Answer:

   To efficiently keep track of the top K elements by frequency -> Option D

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps smallest frequency on top for quick removal [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple array storage
• Assuming heap removes duplicates automatically

2. Which of the following is the correct way to create a min-heap in JavaScript using a priority queue for frequencies?

easy

A. const heap = new MinHeap(x => x.frequency);

B. const heap = new PriorityQueue(x => x.frequency);

C. const heap = new MinPriorityQueue({ priority: x => x.frequency });

D. const heap = new PriorityQueue({ compare: (a,b) => a.frequency - b.frequency });

Solution

1. Step 1: Identify correct syntax for min-heap in JavaScript

   Using the standard library or popular libraries, MinPriorityQueue with a priority function is the correct way.

2. Step 2: Check options for correct constructor and priority function

   const heap = new MinPriorityQueue({ priority: x => x.frequency }); uses new MinPriorityQueue({ priority: x => x.frequency }), which is the correct modern syntax.

3. Final Answer:

   const heap = new MinPriorityQueue({ priority: x => x.frequency }); -> Option C

4. Quick Check:

   MinPriorityQueue with priority function = const heap = new MinPriorityQueue({ priority: x => x.frequency }); [OK]

Hint: Use MinPriorityQueue with priority callback for min-heap [OK]

Common Mistakes:

• Using PriorityQueue without specifying min or max
• Passing compare function incorrectly
• Using non-existent MinHeap constructor

3. What will be the output of the following code snippet?

const nums = [1,1,1,2,2,3];
const k = 2;

// Frequency map
const freqMap = new Map();
for (const num of nums) {
  freqMap.set(num, (freqMap.get(num) || 0) + 1);
}

// Min heap simulation using array and sort
const heap = [];
for (const [num, freq] of freqMap.entries()) {
  heap.push([num, freq]);
  heap.sort((a, b) => a[1] - b[1]);
  if (heap.length > k) heap.shift();
}

const result = heap.map(x => x[0]);
console.log(result);

medium

A. [2, 3]

B. [2, 1]

C. [1, 3]

D. [3, 2]

Solution

1. Step 1: Build frequency map

   nums = [1,1,1,2,2,3] gives freqMap: {1:3, 2:2, 3:1}.

2. Step 2: Use min heap simulation to keep top 2 frequent

   Insert [1,3], heap=[(1,3)]; insert [2,2], heap=[(2,2),(1,3)] sorted by freq ascending; insert [3,1], heap=[(3,1),(2,2),(1,3)] then remove smallest freq (3,1), heap=[(2,2),(1,3)].

3. Final Answer:

   [2, 1] -> Option B

4. Quick Check:

   Top 2 frequent = [2, 1] [OK]

Hint: Keep heap size ≤ k, remove smallest freq element [OK]

Common Mistakes:

• Not sorting heap after each insertion
• Removing wrong element when heap size exceeds k
• Confusing element and frequency order

4. Identify the bug in this code snippet for finding top K frequent elements:

const nums = [4,4,4,6,6,7];
const k = 2;
const freqMap = new Map();
for (const num of nums) {
  freqMap.set(num, freqMap.get(num) + 1);
}

const heap = [];
for (const [num, freq] of freqMap.entries()) {
  heap.push([num, freq]);
  heap.sort((a, b) => a[1] - b[1]);
  if (heap.length > k) heap.shift();
}

const result = heap.map(x => x[0]);
console.log(result);

medium

A. freqMap.get(num) + 1 causes error when key is missing

B. Heap sorting should be descending, not ascending

C. k should be larger than array length

D. Using Map instead of Object for frequency map

Solution

1. Step 1: Check frequency map update logic

   freqMap.get(num) + 1 fails when num is not yet in map, because freqMap.get(num) returns undefined, causing NaN.

2. Step 2: Correct way to update frequency

   Use freqMap.get(num) || 0 to default to 0 if key missing, then add 1.

3. Final Answer:

   freqMap.get(num) + 1 causes error when key is missing -> Option A

4. Quick Check:

   Undefined + 1 = NaN error [OK]

Hint: Always default missing map keys to 0 before adding [OK]

Common Mistakes:

• Not initializing frequency count
• Sorting heap in wrong order
• Misunderstanding Map vs Object usage

5. Given an array nums = [5,3,1,1,1,3,73,1] and k = 2, which approach correctly returns the top K frequent elements using a min-heap? Choose the best code snippet.

A:
const freqMap = new Map();
for (const n of nums) freqMap.set(n, (freqMap.get(n) || 0) + 1);
const heap = [];
for (const [num, freq] of freqMap.entries()) {
  heap.push([num, freq]);
  heap.sort((a,b) => a[1] - b[1]);
  if (heap.length > k) heap.shift();
}
return heap.map(x => x[0]);

B:
const freqMap = {};
for (const n of nums) freqMap[n] = freqMap[n] + 1;
const heap = new MinPriorityQueue({ priority: x => x[1] });
for (const [num, freq] of Object.entries(freqMap)) {
  heap.enqueue([num, freq]);
  if (heap.size() > k) heap.dequeue();
}
const result = [];
while (!heap.isEmpty()) result.push(heap.dequeue()[0]);
return result;

C:
const freqMap = new Map();
for (const n of nums) freqMap.set(n, freqMap.get(n) + 1);
const heap = [];
for (const [num, freq] of freqMap.entries()) {
  heap.push([num, freq]);
  heap.sort((a,b) => b[1] - a[1]);
  if (heap.length > k) heap.pop();
}
return heap.map(x => x[0]);

D:
const freqMap = new Map();
for (const n of nums) freqMap.set(n, (freqMap.get(n) || 0) + 1);
const heap = new MaxPriorityQueue({ priority: x => x[1] });
for (const [num, freq] of freqMap.entries()) {
  heap.enqueue([num, freq]);
  if (heap.size() > k) heap.dequeue();
}
const result = [];
while (!heap.isEmpty()) result.push(heap.dequeue()[0]);
return result;

hard

A. Option A is correct and uses array sort as min-heap simulation

B. Option B is correct using MinPriorityQueue with proper frequency map

C. Option C is correct using max-heap and popping largest frequency

D. Option D is correct using MaxPriorityQueue but removes wrong elements

Solution

1. Step 1: Verify frequency map in each option

   A: Uses Map with (get(n) || 0) + 1 -> correct. B: Object freqMap[n] = freqMap[n] + 1 -> undefined + 1 = NaN -> incorrect. C: Map.set(n, get(n) + 1) -> NaN -> incorrect. D: Map with || 0 -> correct.

2. Step 2: Verify heap logic for keeping top K largest frequencies

   Min-heap keeps size ≤ k by removing smallest freq. A: Sort ascending freq, shift smallest -> correct. B: MinPriorityQueue on freq, dequeue smallest -> correct logic. C: Sort descending, pop largest -> removes largest -> wrong. D: MaxPriorityQueue dequeues largest -> wrong.

3. Step 3: Overall correctness

   Frequencies: 1:4, 3:2, 5:1, 73:1. Top K: 1,3. Only A has correct freq map and heap logic, returns [3,1]. B,C fail on freq map; C,D wrong logic.

4. Final Answer:

   Option A is correct and uses array sort as min-heap simulation -> Option A

5. Quick Check:

   Correct freq + min-heap sim = Option A is correct and uses array sort as min-heap simulation [OK]

Hint: Use MinPriorityQueue with frequency map and size limit k [OK]

Common Mistakes:

• Not initializing frequency counts in object
• Using max-heap instead of min-heap for top K
• Using array sort instead of heap for efficiency