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.