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

Top K Frequent Elements Using Heap

📖 Scenario: You are working on a music app that tracks how many times each song is played. You want to find the top k most played songs to show on the homepage.

🎯 Goal: Build a program that finds the top k frequent elements from a list of numbers using a heap data structure.

📋 What You'll Learn

Create a frequency map of elements from the given array

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

Extract the top k elements from the heap

Print the result array of top k frequent elements

💡 Why This Matters

🌍 Real World

Finding the most popular items, songs, or search queries is common in apps and websites to personalize content or show trending data.

💼 Career

Understanding frequency counting and heap data structures is important for software engineers working on recommendation systems, search engines, and data analytics.

1

Create the frequency map

Create a dictionary called frequencyMap that counts how many times each number appears in the array nums which is [1,1,1,2,2,3].

DSA Javascript

const nums = [1,1,1,2,2,3];
// Create frequencyMap to count occurrences of each number
// Your code here

Hint

Use a for...of loop to go through nums. For each number, add or update its count in frequencyMap.

2

Set the value of k

Create a variable called k and set it to 2 to find the top 2 frequent elements.

DSA Javascript

const nums = [1,1,1,2,2,3];
const frequencyMap = {};
for (const num of nums) {
    frequencyMap[num] = (frequencyMap[num] || 0) + 1;
}
// Set k to 2
// Your code here

Hint

Just create a constant k and assign it the value 2.

3

Use a min-heap to find top k frequent elements

Create an empty array called minHeap to act as a min-heap. Then, iterate over frequencyMap entries using for (const [num, freq] of Object.entries(frequencyMap)). For each entry, push an object {num: Number(num), freq} into minHeap. If minHeap.length exceeds k, remove the element with the smallest frequency. Use a helper function heapify() to maintain the min-heap property after each insertion or removal. Implement heapify() inside the code to keep the smallest frequency element at the root.

DSA Javascript

const nums = [1,1,1,2,2,3];
const frequencyMap = {};
for (const num of nums) {
    frequencyMap[num] = (frequencyMap[num] || 0) + 1;
}
const k = 2;
// Create minHeap array
const minHeap = [];
// Define heapify function
function heapify() {
    // Your code here
}
// Iterate frequencyMap and maintain minHeap of size k
for (const [num, freq] of Object.entries(frequencyMap)) {
    // Your code here
}

Hint

Use an array minHeap and sort it by frequency after each insertion. Remove the smallest frequency element if size exceeds k.

4

Print the top k frequent elements

Create an array called result by mapping minHeap to extract only the num values. Then, print result using console.log(result).

DSA Javascript

const nums = [1,1,1,2,2,3];
const frequencyMap = {};
for (const num of nums) {
    frequencyMap[num] = (frequencyMap[num] || 0) + 1;
}
const k = 2;

const minHeap = [];

function heapify() {
    minHeap.sort((a, b) => a.freq - b.freq);
}

for (const [num, freq] of Object.entries(frequencyMap)) {
    minHeap.push({num: Number(num), freq});
    heapify();
    if (minHeap.length > k) {
        minHeap.shift();
    }
}
// Create result array with only numbers
// Print result
// Your code here

Hint

Map minHeap to get only the num values and print the array.