Top K Frequent Elements Using Heap in DSA Javascript - Execution Trace

Concept Flow - Top K Frequent Elements Using Heap

Count frequencies

↓

For each element frequency

↓

If heap size < k

↓

Else if current freq > min freq in heap

↓

Pop min freq

↓

After all elements processed

↓

Extract elements from heap → Result

Count how often each element appears, keep top k frequent elements in a small heap, then extract them.

Execution Sample

DSA Javascript

const topKFrequent = (nums, k) => {
  const freqMap = new Map();
  for (const n of nums) freqMap.set(n, (freqMap.get(n) || 0) + 1);
  const heap = new MinHeap();
  for (const [num, freq] of freqMap) {
    if (heap.size() < k) heap.push([freq, num]);
    else if (freq > heap.peek()[0]) {
      heap.pop();
      heap.push([freq, num]);
    }
  }
  return heap.toArray().map(x => x[1]);
};

This code finds the top k frequent elements by counting frequencies and using a min-heap to keep track of the top k.

Execution Table

Step	Operation	Frequency Map	Heap Content (freq,num)	Heap Visual State
1	Count frequencies from nums=[1,1,1,2,2,3]	{1:3, 2:2, 3:1}	[]	Empty heap
2	Push (3,1) to heap (heap size < k=2)	{1:3, 2:2, 3:1}	[(3,1)]	Heap: (3,1)
3	Push (2,2) to heap (heap size < k=2)	{1:3, 2:2, 3:1}	[(2,2), (3,1)]	Heap: (2,2) root, (3,1) child
4	Check (1,3), freq=1 <= min freq in heap=2, skip	{1:3, 2:2, 3:1}	[(2,2), (3,1)]	Heap unchanged
5	Extract elements from heap	{1:3, 2:2, 3:1}	[(2,2), (3,1)]	Result elements: [2,1]

💡 All elements processed, heap contains top 2 frequent elements

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
freqMap	{}	{1:3, 2:2, 3:1}	{1:3, 2:2, 3:1}	{1:3, 2:2, 3:1}	{1:3, 2:2, 3:1}	{1:3, 2:2, 3:1}
heap	[]	[]	[(3,1)]	[(2,2), (3,1)]	[(2,2), (3,1)]	[(2,2), (3,1)]

Key Moments - 2 Insights

Why do we use a min-heap of size k instead of a max-heap?

Using a min-heap of size k keeps the smallest frequency at the root, so when a new element with higher frequency comes, we can easily remove the smallest and keep only top k. This is shown in step 3 and 4 of the execution_table.

What happens if the frequency of the current element is less than or equal to the min frequency in the heap?

We skip adding it to the heap because it is not among the top k frequent elements. This is shown in step 4 where (1,3) is skipped.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the heap content?

A [(3,1), (2,2)]

B [(3,1), (3,1)]

C [(2,2), (3,1)]

D [(3,1)]

💡 Hint

Check the 'Heap Content' column at step 3 in execution_table

At which step does the algorithm decide to skip adding an element to the heap?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look for the step where the frequency is less than or equal to the min frequency in the heap

If k was 3 instead of 2, what would be the heap size after processing all elements?

A 1

B 3

C 2

D 4

💡 Hint

Refer to variable_tracker 'heap' row and consider heap size limit k

Concept Snapshot

Top K Frequent Elements Using Heap:
- Count frequencies of elements
- Use a min-heap of size k to keep top k frequent elements
- For each element frequency:
  - If heap size < k, push element
  - Else if freq > min freq in heap, pop min and push new
- Extract elements from heap for result

Full Transcript

This concept shows how to find the top k frequent elements in an array using a min-heap. First, count how many times each element appears. Then, keep a min-heap of size k to store the elements with the highest frequencies. For each element, if the heap is not full, add it. If the heap is full and the current element's frequency is higher than the smallest frequency in the heap, remove the smallest and add the current. Finally, extract the elements from the heap to get the top k frequent elements.

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