Why Top K Frequent Elements Using Heap in DSA Javascript?

The Big Idea

Discover how heaps can magically find the most popular things fast, even in huge piles of data!

The Scenario

Imagine you have a huge list of words from a book, and you want to find the top 3 most common words. Doing this by counting each word manually on paper would take forever and be very confusing.

The Problem

Manually counting each word and then sorting them is slow and easy to mess up. If the list is very long, it becomes impossible to keep track without mistakes or missing some words.

The Solution

Using a heap (a special tree structure) helps us keep track of the top frequent words efficiently. We can quickly add words and remove the least frequent ones, so we only keep the top K at any time.

Before vs After

✗ Before

const counts = {};
for (const word of words) {
  counts[word] = (counts[word] || 0) + 1;
}
const sorted = Object.entries(counts).sort((a, b) => b[1] - a[1]);
const topK = sorted.slice(0, k).map(entry => entry[0]);

✓ After

const counts = new Map();
for (const word of words) {
  counts.set(word, (counts.get(word) || 0) + 1);
}
const minHeap = new MinHeap();
for (const [word, freq] of counts.entries()) {
  minHeap.insert({word, freq});
  if (minHeap.size() > k) minHeap.extractMin();
}
const topK = minHeap.toArray().map(item => item.word);

What It Enables

This method lets you find the most frequent items quickly even in huge data sets, saving time and effort.

Real Life Example

Search engines use this to find the most popular search terms in real time, so they can show trending topics instantly.

Key Takeaways

Manual counting and sorting is slow and error-prone for large data.

Heap keeps track of top K frequent elements efficiently.

Enables fast retrieval of most common items in big lists.

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