Top K Frequent Elements Using Heap in DSA Java - 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

↓

Ignore

↓

Heap contains top k frequent

↓

Extract elements from heap

↓

Return result

Count frequencies, keep top k elements in a min-heap by frequency, then extract them.

Execution Sample

DSA Java

int[] nums = {1,1,1,2,2,3};
int k = 2;
// Count freq: {1:3, 2:2, 3:1}
// Build min-heap size 2
// Process frequencies
// Result: [1,2]

Find top 2 frequent elements from array using min-heap.

Execution Table

Step	Operation	Element Processed	Heap Size	Heap Content (freq, elem)	Action Taken
1	Count frequencies	1	-	-	Frequency map updated: 1 -> 1
2	Count frequencies	1	-	-	Frequency map updated: 1 -> 2
3	Count frequencies	1	-	-	Frequency map updated: 1 -> 3
4	Count frequencies	2	-	-	Frequency map updated: 2 -> 1
5	Count frequencies	2	-	-	Frequency map updated: 2 -> 2
6	Count frequencies	3	-	-	Frequency map updated: 3 -> 1
7	Build heap	-	0	[]	Start with empty min-heap
8	Process frequency	1 (freq=3)	0	[]	Heap size < k, add (3,1)
9	Process frequency	2 (freq=2)	1	[(3,1)]	Heap size < k, add (2,2)
10	Process frequency	3 (freq=1)	2	[(2,2),(3,1)]	Compare freq 1 with heap root freq 2
11	Process frequency	3 (freq=1)	2	[(2,2),(3,1)]	Freq 1 < root freq 2? Yes, ignore element 3
12	Extract result	-	2	[(2,2),(3,1)]	Extract elements: 2 and 1
13	Return result	-	-	-	Top k frequent elements: [1,2]

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

Variable Tracker

Variable	Start	After Step 6	After Step 9	After Step 11	Final
frequency_map	{}	{1=3, 2=2, 3=1}	{1=3, 2=2, 3=1}	{1=3, 2=2, 3=1}	{1=3, 2=2, 3=1}
min_heap	[]	[]	[(3,1),(2,2)]	[(3,1),(2,2)]	[(3,1),(2,2)]
heap_size	0	0	2	2	2

Key Moments - 3 Insights

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

Using a min-heap of size k keeps only the top k frequent elements by always removing the smallest frequency when a new higher frequency comes in, as shown in steps 10-11 where element with freq 1 is ignored because heap root freq 2 is larger.

Why do we ignore elements with frequency less than the heap root frequency?

Because the heap root holds the smallest frequency among the top k elements, any element with smaller frequency cannot be in the top k, as seen in step 11 where element 3 with freq 1 is ignored.

What happens if the input array is empty?

The frequency map remains empty and the heap stays empty, so the result is an empty list. This is implied by the initial empty states in steps 1 and 7.

Visual Quiz - 3 Questions

Look at the execution table at step 10, what is the heap content before processing element 3?

A [(3,1)]

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

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

D []

💡 Hint

Check the 'Heap Content' column at step 10 in the execution_table.

At which step does the heap reach size k?

A Step 9

B Step 8

C Step 7

D Step 10

💡 Hint

Look at the 'Heap Size' column in execution_table to see when it becomes 2 (k=2).

If k was 3 instead of 2, what would happen at step 11?

A Heap size would remain 2

B Element 3 would still be ignored

C Element 3 would be added to the heap

D Heap would be emptied

💡 Hint

With k=3, heap size < k at step 11, so element 3 would be added (see steps 8-9 for adding when heap size < 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 frequency:
  - If heap size < k, add element
  - Else if frequency > min in heap, replace min
- Extract elements from heap for result
- Efficient for large data with limited k

Full Transcript

This visualization shows how to find the top k frequent elements using a min-heap. First, we count how many times each element appears. Then, we build a min-heap that holds at most k elements. For each element's frequency, if the heap is not full, we add it. If the heap is full, we compare the new frequency with the smallest frequency in the heap. If the new frequency is bigger, we remove the smallest and add the new one. Otherwise, we ignore it. At the end, the heap contains the top k frequent elements. This method is efficient because the heap size never grows beyond k. The execution table tracks each step, showing how the heap changes and which elements are added or ignored. The variable tracker shows the frequency map and heap size changes. Key moments clarify why a min-heap is used and why some elements are ignored. The quiz tests understanding of heap content and behavior at different steps.

Practice

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

easy

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

B. To sort all elements in ascending order

C. To store elements without any order

D. To remove duplicates from the list

Solution

1. Step 1: Understand the role of a heap

   A heap is a special tree-based data structure that helps quickly find the smallest or largest element.

2. Step 2: Apply heap to top K frequent elements

   Using a min-heap of size K allows us to keep track of the K elements with the highest frequency efficiently.

3. Final Answer:

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

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps smallest or largest element on top for quick access [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Using heap to remove duplicates
• Ignoring frequency counts

2. Which of the following Java code snippets correctly declares a min-heap to store integer frequencies for the top K frequent elements problem?

easy

A. PriorityQueue<Integer> minHeap = new PriorityQueue<>();

B. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> b - a);

D. PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);

Solution

1. Step 1: Understand Java PriorityQueue default behavior

   By default, PriorityQueue is a min-heap, ordering elements in ascending order.

2. Step 2: Check comparator for min-heap with custom size

   The comparator (a, b) -> a - b keeps the natural ascending order, suitable for min-heap.

3. Final Answer:

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b); -> Option D

4. Quick Check:

   Comparator a-b = min-heap [OK]

Hint: Use (a, b) -> a - b for min-heap comparator in Java [OK]

Common Mistakes:

• Using reverseOrder() creates max-heap, not min-heap
• Wrong comparator sign reverses heap order
• Not specifying initial capacity k is okay but less efficient

3. What will be the output of the following Java code snippet that finds the top 2 frequent elements?

int[] nums = {1,1,1,2,2,3};
int k = 2;
Map freqMap = new HashMap<>();
for (int num : nums) freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));
for (int key : freqMap.keySet()) {
    minHeap.offer(key);
    if (minHeap.size() > k) minHeap.poll();
}
List<Integer> result = new ArrayList<>();
while (!minHeap.isEmpty()) result.add(minHeap.poll());
Collections.reverse(result);
System.out.println(result);

medium

A. [2, 1]

B. [1, 2]

C. [1, 3]

D. [3, 2]

Solution

1. Step 1: Calculate frequencies

   Frequencies: 1 -> 3 times, 2 -> 2 times, 3 -> 1 time.

2. Step 2: Use min-heap to keep top 2 frequent elements

   Heap keeps smallest frequency on top. Insert keys: 1(3), 2(2), 3(1). When size > 2, remove smallest frequency. After all insertions, heap contains 1 and 2.

3. Step 3: Extract and reverse result

   Polling heap gives [2,1], reversing gives [1,2].

4. Final Answer:

   [1, 2] -> Option B

5. Quick Check:

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

Hint: Heap keeps least frequent; remove to keep top K [OK]

Common Mistakes:

• Not reversing the result list
• Confusing min-heap with max-heap behavior
• Ignoring frequency counts in comparator

4. Identify the error in the following Java code snippet for finding top K frequent elements:

int[] nums = {4,4,4,6,6,7};
int k = 2;
Map freqMap = new HashMap<>();
for (int num : nums) freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> freqMap.get(b) - freqMap.get(a));
for (int key : freqMap.keySet()) {
    minHeap.offer(key);
    if (minHeap.size() > k) minHeap.poll();
}
List<Integer> result = new ArrayList<>();
while (!minHeap.isEmpty()) result.add(minHeap.poll());
System.out.println(result);

medium

A. Frequency map is not updated correctly

B. Heap size check condition is incorrect

C. Comparator reverses order causing max-heap instead of min-heap

D. Result list is not reversed before printing

Solution

1. Step 1: Analyze comparator in PriorityQueue

   The comparator (a, b) -> freqMap.get(b) - freqMap.get(a) creates a max-heap (largest frequency on top).

2. Step 2: Understand heap usage for top K frequent elements

   We need a min-heap to remove the smallest frequency when size exceeds k, but max-heap removes largest, causing wrong elements to be removed.

3. Step 3: Identify the error

   The comparator should be (a, b) -> freqMap.get(a) - freqMap.get(b) for min-heap behavior.

4. Final Answer:

   Comparator reverses order causing max-heap instead of min-heap -> Option C

5. Quick Check:

   Wrong comparator = max-heap error [OK]

Hint: Min-heap comparator: a-b; max-heap: b-a [OK]

Common Mistakes:

• Using max-heap instead of min-heap for top K
• Not reversing result list after polling
• Incorrect frequency counting

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 heap? Choose the best sequence of steps.

hard

A. Count frequencies, use min-heap of size k with frequency comparator, add elements, remove smallest when size > k, then extract result

B. Use a hash set to store unique elements, then pick any k elements

C. Sort array, pick last k elements directly

D. Count frequencies, use max-heap to store all elements, poll k times for top elements

Solution

1. Step 1: Count frequencies of elements

   Frequencies: 1 -> 4 times, 3 -> 2 times, 5 -> 1 time, 73 -> 1 time.

2. Step 2: Use min-heap of size k with frequency comparator

   Insert elements into min-heap; if size exceeds k, remove smallest frequency element to keep top k frequent elements.

3. Step 3: Extract elements from heap for result

   After processing, heap contains elements with highest frequencies: 1 and 3.

4. Final Answer:

   Count frequencies, use min-heap of size k with frequency comparator, add elements, remove smallest when size > k, then extract result -> Option A

5. Quick Check:

   Min-heap size k keeps top K frequent [OK]

Hint: Use min-heap size k to keep top frequent elements [OK]

Common Mistakes:

• Using max-heap and polling k times is less efficient
• Sorting array ignores frequency counts
• Using hash set loses frequency info