Top K Frequent Elements Using Heap in DSA C

Mental Model

We want to find the K numbers that appear most often in a list by counting frequencies and using a special structure to keep track of the top counts.

Analogy: Imagine you have a bag of colored balls and you want to find the top K colors that appear most. You count how many balls of each color you have, then keep only the top K counts on a scoreboard that quickly shows the smallest count on top so you can replace it if a bigger count comes.

Input array: [1, 1, 1, 2, 2, 3]
Frequency map: {1:3, 2:2, 3:1}
Min-heap (size K=2):
  2 (freq 2)
 / 
1(freq 3)
Top K frequent elements: [2, 1]

Dry Run Walkthrough

Input: array: [1, 1, 1, 2, 2, 3], k=2

Goal: Find the 2 numbers that appear most frequently in the array

Step 1: Count frequency of each element

Frequency map: {1:3, 2:2, 3:1}

Why: We need to know how often each number appears to find the top K frequent

Step 2: Insert (1,3) into min-heap

Min-heap: [(1,3)]

Why: Start building heap with first frequency

Step 3: Insert (2,2) into min-heap

Min-heap: [(2,2), (1,3)]

Why: Add second frequency; heap keeps smallest frequency on top

Step 4: Skip (3,1) since freq 1 <= root freq 2

Min-heap: [(2,2), (1,3)]

Why: Keep heap size at k by discarding frequencies <= smallest in heap

Result:

Min-heap: [(2,2), (1,3)]
Top K frequent elements: [2, 1]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

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

// Min-heap structure
typedef struct {
    HeapNode *arr;
    int size;
    int capacity;
} MinHeap;

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

// Heapify down from index i
void heapifyDown(MinHeap *heap, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < heap->size && heap->arr[left].freq < heap->arr[smallest].freq)
        smallest = left;
    if (right < heap->size && heap->arr[right].freq < heap->arr[smallest].freq)
        smallest = right;

    if (smallest != i) {
        swap(&heap->arr[i], &heap->arr[smallest]);
        heapifyDown(heap, smallest);
    }
}

// Heapify up from index i
void heapifyUp(MinHeap *heap, int i) {
    int parent = (i - 1) / 2;
    if (i && heap->arr[i].freq < heap->arr[parent].freq) {
        swap(&heap->arr[i], &heap->arr[parent]);
        heapifyUp(heap, parent);
    }
}

// Insert node into heap
void insertHeap(MinHeap *heap, HeapNode node) {
    if (heap->size == heap->capacity) {
        if (node.freq <= heap->arr[0].freq) {
            return; // Do not insert if frequency is not higher
        }
        heap->arr[0] = node; // Replace root
        heapifyDown(heap, 0);
    } else {
        heap->arr[heap->size] = node;
        heapifyUp(heap, heap->size);
        heap->size++;
    }
}

// Create min heap
MinHeap* createMinHeap(int capacity) {
    MinHeap *heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->arr = (HeapNode*)malloc(sizeof(HeapNode) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

// Simple hash map for frequency counting (fixed size for simplicity)
#define MAX_NUM 10000

int* countFrequency(int* nums, int numsSize) {
    int *freq = (int*)calloc(MAX_NUM, sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        freq[nums[i]]++;
    }
    return freq;
}

// Find top K frequent elements
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
    int *freq = countFrequency(nums, numsSize);
    MinHeap *heap = createMinHeap(k);

    for (int i = 0; i < MAX_NUM; i++) {
        if (freq[i] > 0) {
            HeapNode node = {i, freq[i]};
            insertHeap(heap, node);
        }
    }

    int *result = (int*)malloc(sizeof(int) * heap->size);
    for (int i = 0; i < heap->size; i++) {
        result[i] = heap->arr[i].num;
    }
    *returnSize = heap->size;

    free(freq);
    free(heap->arr);
    free(heap);

    return result;
}

int main() {
    int nums[] = {1, 1, 1, 2, 2, 3};
    int k = 2;
    int returnSize = 0;
    int *topK = topKFrequent(nums, 6, k, &returnSize);

    for (int i = 0; i < returnSize; i++) {
        printf("%d", topK[i]);
        if (i != returnSize - 1) printf(" ");
    }
    printf("\n");
    free(topK);
    return 0;
}

freq[nums[i]]++;

count frequency of each number

insertHeap(heap, node);

insert frequency node into min-heap, keep size at k

if (heap->size == heap->capacity) { ... } else { ... }

replace root if new frequency is higher, else insert new node

result[i] = heap->arr[i].num;

collect top k frequent elements from heap

Output

2 1

Complexity Analysis

Time: O(n + m log k) because counting frequencies takes O(n), and inserting m unique elements into a heap of size k takes O(m log k)

Space: O(m + k) where m is number of unique elements for frequency map and heap storage

vs Alternative: Using sorting on all frequencies would take O(m log m), which is slower than heap approach when k << m

Edge Cases

empty array

returns empty result without error

DSA C

for (int i = 0; i < MAX_NUM; i++) { if (freq[i] > 0) { ... } }

k greater than number of unique elements

returns all unique elements without error

DSA C

MinHeap *heap = createMinHeap(k); *returnSize = heap->size;

all elements have same frequency

returns any k elements among them

DSA C

insertHeap function logic to maintain min-heap

When to Use This Pattern

When asked to find the top K frequent items in a large list, use a min-heap to keep track of the top K frequencies efficiently.

Common Mistakes

Mistake: Not maintaining heap size at k, causing extra memory use and wrong results
Fix: Check heap size and replace root if new frequency is higher to keep size at k

Summary

Finds the K most frequent elements in a list using a frequency map and a min-heap.

Use when you need the top K frequent items efficiently without sorting all elements.

Keep a min-heap of size K to track the top frequencies, replacing the smallest when a bigger frequency appears.

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