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

Top K Frequent Elements Using Heap

📖 Scenario: Imagine you have a list of product IDs sold in a store. You want to find the top k products that were sold most frequently to decide which products to promote.

🎯 Goal: Build a C++ program that finds the top k most frequent elements from a list of integers using a heap (priority queue).

📋 What You'll Learn

Create a vector called nums with the exact values: {1,1,1,2,2,3}

Create an integer variable called k and set it to 2

Use a unordered_map<int, int> called freq to count frequencies of elements in nums

Use a priority_queue (min-heap) to keep track of top k frequent elements

Print the top k frequent elements in any order

💡 Why This Matters

🌍 Real World

Finding the most popular products, words, or items in large datasets is common in marketing, search engines, and recommendation systems.

💼 Career

Understanding heaps and frequency counting is important for roles in software development, data analysis, and algorithm design.

1

Create the data vector

Create a std::vector<int> called nums with these exact values: {1,1,1,2,2,3}

DSA C++

# Your code here

Hint

Use std::vector<int> nums = {1,1,1,2,2,3}; to create the list.

2

Add the variable for k

Add an integer variable called k and set it to 2 below the nums vector

DSA C++

#include 
#include 

int main() {
    std::vector nums = {1,1,1,2,2,3};
    // Your code here
    return 0;
}

Hint

Write int k = 2; to set how many top elements to find.

3

Count frequencies and use a min-heap

Create an unordered_map<int, int> called freq to count frequencies of elements in nums. Then use a priority_queue as a min-heap to keep top k frequent elements. Use for loops with variables num and p as needed.

DSA C++

#include 
#include 
#include 
#include 

int main() {
    std::vector nums = {1,1,1,2,2,3};
    int k = 2;
    // Your code here
    return 0;
}

Hint

Use freq[num]++ to count. Use a min-heap with a custom comparator to keep top k frequent elements.

4

Print the top k frequent elements

Use a while loop to pop elements from minHeap and print the first value of each pair (the element) separated by spaces.

DSA C++

#include 
#include 
#include 
#include 

int main() {
    std::vector nums = {1,1,1,2,2,3};
    int k = 2;

    std::unordered_map freq;
    for (int num : nums) {
        freq[num]++;
    }

    auto cmp = [](const std::pair& a, const std::pair& b) {
        return a.second > b.second;
    };
    std::priority_queue, std::vector>, decltype(cmp)> minHeap(cmp);

    for (auto p : freq) {
        minHeap.push(p);
        if ((int)minHeap.size() > k) {
            minHeap.pop();
        }
    }

    // Print top k frequent elements
    // Your code here
    return 0;
}

Hint

Pop from minHeap until empty and print the element part of each pair.

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 requires finding the k elements that appear most frequently.

2. Step 2: Role of heap in this context

   A heap helps efficiently keep track of the top k frequent elements by maintaining a structure where the smallest frequency is easily accessible and can be replaced if a more frequent element is found.

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 array storage
• Assuming heap removes duplicates

2. Which of the following C++ STL containers is best suited to implement a min-heap for the Top K Frequent Elements problem?

easy

A. std::vector with std::make_heap and std::pop_heap

B. std::list

C. std::map

D. std::queue

Solution

1. Step 1: Identify heap implementation in C++ STL

   C++ STL uses a vector with heap algorithms like std::make_heap, std::pop_heap, and std::push_heap to implement heaps.

2. Step 2: Check other container suitability

   std::list and std::queue do not support heap operations directly. std::map is a balanced tree, not a heap.

3. Final Answer:

   std::vector with std::make_heap and std::pop_heap -> Option A

4. Quick Check:

   Vector + heap algorithms = min-heap [OK]

Hint: Use vector + heap functions for heap in C++ [OK]

Common Mistakes:

• Choosing std::map thinking it is a heap
• Using std::queue which is FIFO, not heap
• Using std::list which lacks random access

3. What is the output of the following C++ code snippet for nums = {1,1,1,2,2,3} and k = 2?

std::vector<int> nums = {1,1,1,2,2,3};
int k = 2;
// Frequency map
std::unordered_map freq;
for (int n : nums) freq[n]++;

// Min heap to store pairs (frequency, element)
std::priority_queue, std::vector>, std::greater<>> minHeap;

for (auto& p : freq) {
    minHeap.push({p.second, p.first});
    if (minHeap.size() > k) minHeap.pop();
}

std::vector<int> result;
while (!minHeap.empty()) {
    result.push_back(minHeap.top().second);
    minHeap.pop();
}
std::reverse(result.begin(), result.end());
for (int x : result) std::cout << x << " ";

medium

A. 3 2

B. 2 3

C. 1 3

D. 1 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

   Insert (3,1), (2,2), (1,3). When size exceeds 2, pop smallest frequency. After all insertions, heap contains (2,2) and (3,1).

3. Step 3: Extract and reverse result

   Extracting gives elements 2 and 1, reversed to 1 2.

4. Final Answer:

   1 2 -> Option D

5. Quick Check:

   Top 2 frequent = 1 and 2 [OK]

Hint: Heap keeps smallest freq; pop when size > k [OK]

Common Mistakes:

• Not reversing the result vector
• Confusing element and frequency in pairs
• Popping wrong element from heap

4. Identify the bug in this code snippet for finding top k frequent elements:

std::unordered_map freq;
for (int n : nums) freq[n]++;

std::priority_queue> maxHeap;
for (auto& p : freq) {
    maxHeap.push({p.second, p.first});
    if (maxHeap.size() > k) maxHeap.pop();
}

std::vector<int> result;
while (!maxHeap.empty()) {
    result.push_back(maxHeap.top().second);
    maxHeap.pop();
}

medium

A. Frequency map is not created correctly

B. Using maxHeap and popping when size > k removes most frequent elements

C. Result vector is not reversed before output

D. Priority queue should store only elements, not pairs

Solution

1. Step 1: Understand heap type and popping logic

   maxHeap stores pairs with highest frequency on top. Popping when size > k removes the top (most frequent) element, which is wrong.

2. Step 2: Correct approach

   Use a minHeap to keep smallest frequency on top and pop it when size > k, so top k frequent remain.

3. Final Answer:

   Using maxHeap and popping when size > k removes most frequent elements -> Option B

4. Quick Check:

   MaxHeap pop removes top freq, wrong for top k [OK]

Hint: Pop from minHeap, not maxHeap, to keep top k [OK]

Common Mistakes:

• Using maxHeap and popping top element
• Not reversing result vector if needed
• Ignoring frequency-element pair structure

5. Given a large input array with many elements having the same frequency, how can you modify the heap approach to ensure the Top K Frequent Elements always returns the smallest elements when frequencies tie? Choose the best approach.

hard

A. Use a hash map only without any heap

B. Use a max-heap ordered by frequency only

C. Use a min-heap ordered by frequency, then by element value descending

D. Sort the entire array before building the heap

Solution

1. Step 1: Understand tie-breaking requirement

   When frequencies tie, we want the smaller element to come first in the top k.

2. Step 2: Modify heap ordering

   Use a min-heap that orders pairs by frequency first, then by element value ascending to break ties correctly.

3. Step 3: Why other options fail

   Max-heap ignores tie-break order, sorting entire array is inefficient, and hash map alone cannot find top k efficiently.

4. Final Answer:

   Use a min-heap ordered by frequency, then by element value ascending -> Option C

5. Quick Check:

   Min-heap with tie-break by element value [OK]

Hint: Tie-break by element value in heap comparator [OK]

Common Mistakes:

• Ignoring tie-break condition in heap
• Sorting entire array wastes time
• Using hash map alone without heap