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

Concept Flow - Top K Frequent Elements Using Heap

Count frequencies

↓

Build min-heap of size k

↓

For each element frequency

↓

If heap size < k

↓

Add element

↓

Heapify

↓

Extract k elements from heap

↓

Return top k frequent elements

Count frequencies, keep a min-heap of size k for top frequencies, then extract results.

Execution Sample

DSA Typescript

const topKFrequent = (nums: number[], k: number): number[] => {
  const freqMap = new Map<number, number>();
  nums.forEach(n => freqMap.set(n, (freqMap.get(n) || 0) + 1));
  const heap: [number, number][] = [];
  // heap operations omitted for brevity
  return heap.map(([freq, num]) => num);
};

Counts frequencies of numbers, uses a min-heap to keep top k frequent elements, returns them.

Execution Table

Step	Operation	Element Processed	Heap Size	Heap Content (freq,num)	Visual State
1	Count frequency of 1	1	0	[]	freqMap={1:1}
2	Count frequency of 1	1	0	[]	freqMap={1:2}
3	Count frequency of 2	2	0	[]	freqMap={1:2,2:1}
4	Count frequency of 3	3	0	[]	freqMap={1:2,2:1,3:1}
5	Add (1,2) to heap	2	1	[(1,2)]	Heap=[(freq=1,num=2)]
6	Add (2,1) to heap	1	2	[(1,2),(2,1)]	Heap=[(freq=1,num=2),(freq=2,num=1)]
7	Add (1,3) to heap	3	3	[(1,2),(2,1),(1,3)]	Heap=[(freq=1,num=2),(freq=2,num=1),(freq=1,num=3)]
8	Heap size > k=2, remove min	-	2	[(1,3),(2,1)]	Removed (1,2), Heap=[(freq=1,num=3),(freq=2,num=1)]
9	Extract elements from heap	-	2	[(1,3),(2,1)]	Top k elements: [3,1]
10	Return result	-	-	[3,1]	Final output: [3,1]

💡 All elements processed and heap contains top k frequent elements.

Variable Tracker

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

Key Moments - 3 Insights

Why do we remove the smallest frequency element when heap size exceeds k?

Because we want to keep only the top k frequent elements. The heap is a min-heap by frequency, so the smallest frequency is at the root. Removing it keeps the heap size at k and ensures only the largest frequencies remain (see Step 8 in execution_table).

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

Using a min-heap of size k lets us efficiently discard less frequent elements. If a new element has frequency higher than the min (root), we replace it. This keeps the heap small and focused on top frequencies (see Steps 5-8).

What happens if k is equal to the number of unique elements?

The heap will contain all unique elements without removals, so all frequencies are kept. The heap size never exceeds k, so no removals occur (see Steps 5-7).

Visual Quiz - 3 Questions

Look at the execution_table at Step 8, which element is removed from the heap?

A (1,2)

B (1,3)

C (2,1)

D (3,1)

💡 Hint

Check the 'Heap Content' and 'Visual State' columns at Step 8.

At which step does the heap first reach size k=2?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Heap Size' column in execution_table.

If the frequency of element 3 was 3 instead of 1, how would the heap content change after Step 7?

A Heap would contain (3,3) and (1,2)

B Heap would contain (1,3) and (2,1)

C Heap would contain (3,3) and (2,1)

D Heap would contain (1,2) and (2,1)

💡 Hint

Higher frequency elements replace smaller ones in the min-heap (see key_moments about heap behavior).

Concept Snapshot

Top K Frequent Elements Using Heap:
- Count frequencies of elements.
- Use a min-heap of size k to track top frequencies.
- Add elements to heap; if size > k, remove smallest frequency.
- Extract elements from heap for result.
- Efficient for large input with many duplicates.

Full Transcript

This visualization shows how to find the top k frequent elements using a min-heap. First, we count how many times each number appears. Then, we build a min-heap that keeps only the k elements with the highest frequencies. When adding a new element, if the heap is smaller than k, we add it directly. If the heap is full and the new element's frequency is higher than the smallest frequency in the heap, we remove the smallest and add the new one. Finally, we extract the elements from the heap to get the top k frequent numbers. The execution table tracks each step, showing frequency counts, heap size, and heap content. Key moments explain why we use a min-heap and why we remove the smallest frequency element when the heap is full. The quiz tests understanding of heap operations and frequency counting.