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

Top K Frequent Elements Using Heap

📖 Scenario: You work in a music app team. You want to find the top K most played songs from a list of song plays. This helps show popular songs to users.

🎯 Goal: Build a Java program that finds the k most frequent elements from an integer array using a heap (priority queue).

📋 What You'll Learn

Create an integer array called plays with exact values

Create an integer variable called k for the number of top elements

Use a HashMap to count frequencies of elements in plays

Use a PriorityQueue as a min-heap to keep top k frequent elements

Print the top k frequent elements in any order

💡 Why This Matters

🌍 Real World

Finding top K frequent elements is common in recommendation systems, search engines, and analytics to highlight popular items.

💼 Career

This skill is useful for software engineers working on data processing, backend services, and machine learning feature engineering.

1

Create the plays array

Create an integer array called plays with these exact values: 4, 1, 2, 2, 3, 3, 3, 4, 4, 4

DSA Java

// Create the plays array with given values
// Your code here

Hint

Use int[] plays = {4, 1, 2, 2, 3, 3, 3, 4, 4, 4}; to create the array.

2

Set the value of k

Create an integer variable called k and set it to 2 to find the top 2 frequent elements

DSA Java

int[] plays = {4, 1, 2, 2, 3, 3, 3, 4, 4, 4};
// Create variable k and set it to 2
// Your code here

Hint

Use int k = 2; to set the number of top elements.

3

Count frequencies and use a min-heap to find top k

Use a HashMap<Integer, Integer> called freqMap to count frequencies of elements in plays. Then create a PriorityQueue<Integer> called minHeap that sorts elements by frequency from freqMap. Add elements to minHeap and keep its size at most k by removing the smallest frequency element.

DSA Java

int[] plays = {4, 1, 2, 2, 3, 3, 3, 4, 4, 4};
int k = 2;
// Count frequencies in freqMap
// Create minHeap with comparator using freqMap
// Add elements to minHeap and keep size <= k
// Your code here

Hint

Use a HashMap to count frequencies. Use a PriorityQueue with a comparator that compares frequencies from the map. Add keys to the heap and remove smallest when size exceeds k.

4

Print the top k frequent elements

Create a list called topK and poll elements from minHeap to add to topK. Then print topK.

DSA Java

import java.util.*;

int[] plays = {4, 1, 2, 2, 3, 3, 3, 4, 4, 4};
int k = 2;

Map freqMap = new HashMap();
for (int num : plays) {
    freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}

PriorityQueue minHeap = new PriorityQueue(Comparator.comparingInt(freqMap::get));
for (int num : freqMap.keySet()) {
    minHeap.offer(num);
    if (minHeap.size() > k) {
        minHeap.poll();
    }
}
// Create list topK and poll from minHeap
// Print topK
// Your code here

Hint

Poll all elements from minHeap into a list and print it. The order can be any order of the top 2 frequent elements.

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