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.