Top K Frequent Elements Using Heap in DSA Python - Build from Scratch

Top K Frequent Elements Using Heap

📖 Scenario: Imagine you run a small online store. You want to find the top k products that customers buy the most. This helps you decide which products to promote or keep in stock.

🎯 Goal: You will build a program that finds the k most frequent elements from a list of product IDs using a heap data structure.

📋 What You'll Learn

Create a list of product IDs with exact values

Create a variable k to specify how many top products to find

Use a dictionary to count the frequency of each product

Use a heap to find the top k frequent products

Print the list of top k frequent products

💡 Why This Matters

🌍 Real World

Finding top selling products helps businesses focus on popular items and manage inventory better.

💼 Career

This technique is useful for data analysis, recommendation systems, and optimizing product displays in e-commerce.

1

Create the product list

Create a list called products with these exact product IDs: 101, 102, 101, 103, 102, 101, 104, 102, 105, 103

DSA Python

# Create the list of product IDs
# Your code here

Hint

Use square brackets [] to create a list and separate numbers with commas.

2

Set the value of k

Create a variable called k and set it to 3 to find the top 3 frequent products.

DSA Python

products = [101, 102, 101, 103, 102, 101, 104, 102, 105, 103]
# Set the value of k
# Your code here

Hint

Use = to assign the number 3 to the variable k.

3

Count frequencies and find top k using heap

Import heapq. Create a dictionary called freq to count how many times each product appears in products. Then use heapq.nlargest with k and freq.get to find the top k frequent products and store them in top_k.

DSA Python

products = [101, 102, 101, 103, 102, 101, 104, 102, 105, 103]
k = 3
# Import heapq and count frequencies
# Use heapq.nlargest to find top k frequent products
# Your code here

Hint

Use a for loop to count frequencies. Use heapq.nlargest(k, freq, key=freq.get) to get the top k keys with highest values.

4

Print the top k frequent products

Print the variable top_k to display the list of top 3 frequent products.

DSA Python

import heapq

products = [101, 102, 101, 103, 102, 101, 104, 102, 105, 103]
k = 3

freq = {}
for product in products:
    freq[product] = freq.get(product, 0) + 1

top_k = heapq.nlargest(k, freq, key=freq.get)
# Print the top_k list
# Your code here

Hint

Use print(top_k) to show the result.

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