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

↓

Return top k frequent elements

Count how often each element appears, keep top k in a small heap, then return those elements.

Execution Sample

DSA Python

nums = [1,1,1,2,2,3]
k = 2
# Count frequencies
# Use min-heap to keep top k
# Extract results

This code finds the 2 most frequent numbers in the list using a min-heap.

Execution Table

Step	Operation	Frequency Map	Heap Content (freq, elem)	Heap Size	Visual Heap State
1	Count frequencies	{1:3, 2:2, 3:1}	[]	0	Empty heap
2	Push (3,1) to heap	{1:3, 2:2, 3:1}	[(3,1)]	1	Heap: (3,1)
3	Push (2,2) to heap	{1:3, 2:2, 3:1}	[(2,2),(3,1)]	2	Heap: (2,2), (3,1)
4	Check (1,3) freq=1 < min freq=2? Yes, no push	{1:3, 2:2, 3:1}	[(2,2),(3,1)]	2	Heap unchanged
5	Extract elements from heap	{1:3, 2:2, 3:1}	[(2,2),(3,1)]	2	Heap unchanged
6	Return elements [1,2]	{1:3, 2:2, 3:1}	[]	0	Heap emptied

💡 All elements processed and top k extracted

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	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}	{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)]	[]
heap_size	0	0	1	2	2	2	0

Key Moments - 3 Insights

Why do we use a min-heap instead of a max-heap for top k frequent elements?

We keep the heap size fixed at k with the smallest frequency at the top. This way, when a new element with higher frequency comes, we can easily remove the smallest frequency element. This is shown in step 3 and 4 of the execution_table where we push elements and compare with the min frequency.

What happens if the heap size is less than k when adding elements?

We simply push the new element into the heap without removing anything, as shown in steps 2 and 3. The heap grows until it reaches size k.

Why do we extract elements from the heap at the end?

The heap contains the top k frequent elements but in heap order, not sorted. Extracting them gives us the final list of top k elements, as shown in step 5 and 6.

Visual Quiz - 3 Questions

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

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

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

C [(3,1)]

D []

💡 Hint

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

At which step does the heap reach size k?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Heap Size' column in execution_table to see when it becomes 2

If k was 1 instead of 2, how would the heap size change after step 3?

A Heap size would be 0

B Heap size would be 2

C Heap size would be 1

D Heap size would be 3

💡 Hint

Refer to variable_tracker heap_size values 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 track top frequencies
- Push elements until heap size k
- If new freq > min in heap, pop min and push new
- Extract elements from heap for result
- Efficient for large data with limited k

Full Transcript

To find the top k frequent elements, first count how many times each element appears. Then, use a min-heap that holds at most k elements. For each element frequency, if the heap is smaller than k, add it. If the heap is full and the new frequency is bigger than the smallest frequency in the heap, remove the smallest and add the new one. After processing all elements, extract the elements from the heap to get the top k frequent elements. This method keeps the heap small and efficient. The execution table shows each step of counting, pushing to heap, and extracting results.

Practice

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

easy

A. To efficiently keep track of the top k 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 problem goal

   The problem asks to find the k elements that appear most frequently in a list.

2. Step 2: Role of heap in this context

   A heap helps efficiently keep track of the top k frequent elements by maintaining a small structure of size k, allowing quick access to the smallest frequency among them.

3. Final Answer:

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

4. Quick Check:

   Heap = Efficient top k tracking [OK]

Hint: Heap keeps smallest frequency on top for quick replacement [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple list or set
• Assuming heap removes duplicates

2. Which of the following Python code snippets correctly creates a min-heap from a list freq_list using the heapq module?

easy

A. import heapq
heapq.makeheap(freq_list)

B. import heapq
heapq.heapify(freq_list)

C. import heapq
heapq.heap(freq_list)

D. import heapq
heapq.create(freq_list)

Solution

1. Step 1: Recall heapq module functions

   The heapq module provides heapify() to convert a list into a heap in-place.

2. Step 2: Identify correct function usage

   Only heapq.heapify(freq_list) is valid syntax to create a min-heap from a list.

3. Final Answer:

   import heapq heapq.heapify(freq_list) -> Option B

4. Quick Check:

   heapify() creates heap [OK]

Hint: Use heapq.heapify() to build a heap from list [OK]

Common Mistakes:

• Using non-existent heapq functions
• Confusing heapify with sorting
• Missing import statement

3. What will be the output of the following code?

import heapq
nums = [1,1,1,2,2,3]
count = {}
for n in nums:
    count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
    heapq.heappush(heap, (freq, num))
result = []
for _ in range(2):
    result.append(heapq.heappop(heap)[1])
print(result)

medium

A. [1, 2]

B. [2, 3]

C. [1, 3]

D. [3, 2]

Solution

1. Step 1: Count frequencies of elements

   nums = [1,1,1,2,2,3] gives count = {1:3, 2:2, 3:1}.

2. Step 2: Push (freq, num) into min-heap and pop twice

   Heap contains (3,1), (2,2), (1,3). Popping twice removes smallest freq first: (1,3), then (2,2). So result = [3, 2].

3. Final Answer:

   [3, 2] -> Option D

4. Quick Check:

   Lowest freq elements popped first = [3, 2] [OK]

Hint: Min-heap pops smallest frequency first [OK]

Common Mistakes:

• Assuming heap pops highest frequency first
• Mixing up element and frequency order
• Not counting frequencies correctly

4. Identify the error in the following code snippet that tries to find the top 2 frequent elements:

import heapq
nums = [4,4,4,5,5,6]
count = {}
for n in nums:
    count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
    heapq.heappush(heap, (num, freq))
result = []
for _ in range(2):
    result.append(heapq.heappop(heap)[1])
print(result)

medium

A. The range in the last loop should be 3 instead of 2

B. The count dictionary is not updated correctly

C. The tuple pushed to heap should be (freq, num), not (num, freq)

D. heapq.heappush is used incorrectly; should use heapq.push

Solution

1. Step 1: Check tuple order pushed to heap

   The heap is a min-heap by first tuple element. Pushing (num, freq) orders by num, not frequency.

2. Step 2: Correct tuple order for frequency sorting

   To get top frequent elements, push (freq, num) so heap orders by frequency.

3. Final Answer:

   The tuple pushed to heap should be (freq, num), not (num, freq) -> Option C

4. Quick Check:

   Heap order depends on first tuple element [OK]

Hint: Push (frequency, element) tuples to heap [OK]

Common Mistakes:

• Swapping frequency and element in tuple
• Using wrong heapq function name
• Incorrect loop range for popping

5. Given the list nums = [2,3,2,4,3,3,5,5,5,5] and k = 2, which of the following code snippets correctly returns the top k frequent elements using a heap?

hard

A. import heapq
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
if len(heap) < k:
heapq.heappush(heap, (freq, num))
else:
if freq > heap[0][0]:
heapq.heapreplace(heap, (freq, num))
result = [num for freq, num in heap]
print(result)

B. import heapq
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
heapq.heappush(heap, (num, freq))
result = [heapq.heappop(heap)[1] for _ in range(k)]
print(result)

C. import heapq
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
heapq.heappush(heap, (-freq, num))
result = [heapq.heappop(heap)[0] for _ in range(k)]
print(result)

D. import heapq
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
if freq < k:
heapq.heappush(heap, (freq, num))
result = [num for freq, num in heap]
print(result)

Solution

1. Step 1: Understand the problem and approach

   We want top k frequent elements using a min-heap of size k to keep track of highest frequencies.

2. Step 2: Analyze each option

   import heapq count = {} for n in nums: count[n] = count.get(n, 0) + 1 heap = [] for num, freq in count.items(): if len(heap) < k: heapq.heappush(heap, (freq, num)) else: if freq > heap[0][0]: heapq.heapreplace(heap, (freq, num)) result = [num for freq, num in heap] print(result) correctly pushes (freq, num) and maintains heap size k, replacing smallest freq when a bigger freq is found. import heapq count = {} for n in nums: count[n] = count.get(n, 0) + 1 heap = [] for num, freq in count.items(): heapq.heappush(heap, (num, freq)) result = [heapq.heappop(heap)[1] for _ in range(k)] print(result) pushes (num, freq) which is wrong order. import heapq count = {} for n in nums: count[n] = count.get(n, 0) + 1 heap = [] for num, freq in count.items(): heapq.heappush(heap, (-freq, num)) result = [heapq.heappop(heap)[1] for _ in range(k)] print(result) uses negative freq but does not maintain heap size k properly. import heapq count = {} for n in nums: count[n] = count.get(n, 0) + 1 heap = [] for num, freq in count.items(): if freq < k: heapq.heappush(heap, (freq, num)) result = [num for freq, num in heap] print(result) pushes only if freq < k which is incorrect logic.

3. Final Answer:

   Option A code correctly returns top k frequent elements -> Option A

4. Quick Check:

   Min-heap size k with freq as key [OK]

Hint: Maintain min-heap size k with (freq, num) tuples [OK]

Common Mistakes:

• Pushing wrong tuple order to heap
• Not limiting heap size to k
• Using negative frequencies without proper logic