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

Top K Frequent Elements Using Heap

📖 Scenario: You are working on a data analysis tool that needs to find the most frequent numbers in a list of integers. This helps in understanding which numbers appear most often, like popular items in a store or common error codes.

🎯 Goal: Build a C program that finds the top k most frequent elements from an array of integers using a heap data structure.

📋 What You'll Learn

Create an integer array called nums with the exact values: 4, 1, 2, 2, 3, 3, 3

Create an integer variable called k and set it to 2

Implement a min-heap to keep track of the top k frequent elements

Print the top k frequent elements in any order

💡 Why This Matters

🌍 Real World

Finding the most frequent items is useful in many areas like analyzing popular products, trending topics, or common errors in logs.

💼 Career

This skill is important for software engineers working with data processing, analytics, and optimization problems.

1

Create the integer array nums

Create an integer array called nums with the exact values 4, 1, 2, 2, 3, 3, 3 and an integer variable numsSize set to 7.

DSA C

int nums[] = {4, 1, 2, 2, 3, 3, 3};
int numsSize = 7;
// Your code here

Hint

Use int nums[] = {4, 1, 2, 2, 3, 3, 3}; to create the array and int numsSize = 7; for its size.

2

Create the variable k

Create an integer variable called k and set it to 2.

DSA C

int nums[] = {4, 1, 2, 2, 3, 3, 3};
int numsSize = 7;
int k = 2;
// Your code here

Hint

Use int k = 2; to create the variable.

3

Implement the core logic to find top k frequent elements using a min-heap

Implement the main logic to find the top k frequent elements from nums using a min-heap. Use a frequency map, then a min-heap to keep track of the top k elements by frequency.

DSA C

int nums[] = {4, 1, 2, 2, 3, 3, 3};
int numsSize = 7;
int k = 2;
// Your code here

Hint

Use a frequency array to count occurrences, then insert elements into a min-heap of size k. Replace the root if a new element has higher frequency.

4

Print the top k frequent elements

Print the top k frequent elements stored in the heap separated by spaces.

DSA C

#include 
#include 

// Structure for heap node
typedef struct {
    int num;
    int freq;
} HeapNode;

// Swap two heap nodes
void swap(HeapNode* a, HeapNode* b) {
    HeapNode temp = *a;
    *a = *b;
    *b = temp;
}

// Min-heapify function
void minHeapify(HeapNode heap[], int size, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  heap[i].freq) {
            swap(&heap[i], &heap[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    } else if (node.freq > heap[0].freq) {
        heap[0] = node;
        minHeapify(heap, *size, 0);
    }
}

int main() {
    int nums[] = {4, 1, 2, 2, 3, 3, 3};
    int numsSize = 7;
    int k = 2;

    // Frequency map using fixed size array for simplicity (range 0-100)
    int freq[101] = {0};
    for (int i = 0; i  0) {
            HeapNode node = {num, freq[num]};
            insertHeap(heap, &heapSize, node, k);
        }
    }

    // Print top k frequent elements
    for (int i = 0; i < heapSize; i++) {
        printf("%d ", heap[i].num);
    }
    printf("\n");

    free(heap);
    return 0;
}

// Your code here

Hint

The output should print the two most frequent numbers separated by a space. The order can be any, but the numbers must be 3 and 2.

Practice

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

easy

A. To efficiently find and maintain the top K frequent elements

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 heap in frequency problems

   A heap helps keep track of the most frequent elements efficiently by allowing quick access to the smallest or largest frequency element.

2. Step 2: Identify why heap is used for top K elements

   Using a min-heap of size K allows us to maintain only the top K frequent elements, removing less frequent ones as we go.

3. Final Answer:

   To efficiently find and maintain the top K frequent elements -> Option A

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps top K elements efficiently by frequency [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Using heap to remove duplicates
• Ignoring frequency counts in heap

2. Which of the following is the correct way to declare a min-heap in C++ using the standard library for storing pairs of (frequency, element)?

easy

A. priority_queue minHeap;

B. priority_queue> minHeap;

C. priority_queue, vector>, greater>> minHeap;

D. priority_queue, vector>, less>> minHeap;

Solution

1. Step 1: Understand C++ priority_queue syntax for min-heap

   By default, priority_queue is a max-heap. To make it min-heap, we use greater comparator.

2. Step 2: Check the correct template parameters

   We need a priority_queue of pairs, with vector as container, and greater> as comparator for min-heap.

3. Final Answer:

   priority_queue, vector>, greater>> minHeap; -> Option C

4. Quick Check:

   Min-heap = priority_queue with greater comparator [OK]

Hint: Use greater comparator for min-heap in priority_queue [OK]

Common Mistakes:

• Using default priority_queue which is max-heap
• Wrong comparator like less instead of greater
• Incorrect container type in priority_queue

3. What will be the output of the following code snippet that finds top 2 frequent elements?

#include 
#include 
#include 

int main() {
    int nums[] = {1,1,1,2,2,3};
    int freq[4] = {0};
    for(int i=0; i<6; i++) freq[nums[i]]++;
    int k = 2;
    int result[2];
    int idx = 0;
    for(int i=1; i<=3; i++) {
        if(idx < k) {
            result[idx++] = i;
        } else {
            int min_idx = 0;
            for(int j=1; j freq[result[min_idx]]) result[min_idx] = i;
        }
    }
    for(int i=0; i

medium

A. 3 2

B. 1 3

C. 2 3

D. 1 2

Solution

1. Step 1: Count frequencies of elements

   nums = {1,1,1,2,2,3} so freq[1]=3, freq[2]=2, freq[3]=1.

2. Step 2: Select top 2 frequent elements using simple logic

   Initially result = {1,2}. For i=3, freq[3]=1 is less than min freq in result (which is freq[2]=2), so no replacement.

3. Final Answer:

   1 2 -> Option D

4. Quick Check:

   Top 2 frequent = 1 and 2 [OK]

Hint: Count frequencies, keep top K by comparing min freq [OK]

Common Mistakes:

• Confusing element values with frequencies
• Replacing elements incorrectly in result array
• Ignoring initial filling of result array

4. Identify the bug in the following code snippet that tries to find top 3 frequent elements using a min-heap approach:

#include 
#include 
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    vector<int> nums = {4,4,4,6,6,7,7,7,7};
    unordered_map freq;
    for(auto n : nums) freq[n]++;
    priority_queue, vector>, greater>> minHeap;
    int k = 3;
    for(auto it : freq) {
        minHeap.push({it.second, it.first});
        if(minHeap.size() > k) minHeap.pop();
    }
    while(!minHeap.empty()) {
        printf("%d ", minHeap.top().second);
        minHeap.pop();
    }
    return 0;
}

medium

A. The condition to pop from heap should be if size >= k, not > k

B. The output order is reversed; elements print from least to most frequent

C. The min-heap should store (element, frequency) pairs, not (frequency, element)

D. The frequency map is not initialized correctly

Solution

1. Step 1: Understand min-heap stores (frequency, element)

   Min-heap keeps smallest frequency on top, so popping prints from least to most frequent.

2. Step 2: Identify output order issue

   Printing while popping will print elements from lowest to highest frequency, not top frequent first.

3. Final Answer:

   The output order is reversed; elements print from least to most frequent -> Option B

4. Quick Check:

   Min-heap pop order = ascending frequency [OK]

Hint: Min-heap pops smallest first, so output order is reversed [OK]

Common Mistakes:

• Confusing pair order in heap
• Wrong pop condition for heap size
• Ignoring output order from heap pops

5. Given an array nums = {5,3,1,1,1,3,73,1} and k = 2, which approach correctly finds the top K frequent elements using a heap and handles ties properly?

hard

A. Use a min-heap of size k with (frequency, element) pairs, replacing when frequency is higher

B. Use a hash map only without any heap

C. Sort the array and pick the last k elements

D. Use a min-heap of (frequency, element) pairs and pop k times

Solution

1. Step 1: Count frequencies of elements

   Frequencies: 1->4, 3->2, 5->1, 73->1.

2. Step 2: Use min-heap of size k to keep top frequent elements

   Insert pairs (freq, element). If heap size exceeds k, pop smallest frequency. This keeps top k frequent elements efficiently.

3. Step 3: Handle ties by frequency naturally in heap

   Elements with same frequency are handled by heap order; ties do not break correctness.

4. Final Answer:

   Use a min-heap of size k with (frequency, element) pairs, replacing when frequency is higher -> Option A

5. Quick Check:

   Min-heap size k keeps top frequent elements [OK]

Hint: Min-heap size k keeps top frequent elements, replacing lower freq [OK]

Common Mistakes:

• Using max-heap and popping k times without size limit
• Sorting array instead of frequencies
• Ignoring heap for frequency tracking