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

Top K Frequent Elements Using Heap

📖 Scenario: Imagine you run a small online store. You want to find the top k products that customers buy most often. This helps you know which products to promote or stock more.

🎯 Goal: You will write a program to find the k most frequent elements from a list of product IDs using a heap (priority queue).

📋 What You'll Learn

Create an array called products with given product IDs.

Create a variable called k to store how many top products to find.

Use a Map to count frequencies of each product.

Use a min-heap (priority queue) to keep track of top k frequent products.

Print the array of top k frequent product IDs.

💡 Why This Matters

🌍 Real World

Finding the most popular products helps businesses focus on best sellers and improve sales.

💼 Career

This technique is useful in data analysis, recommendation systems, and any job involving frequency analysis or priority queues.

1

Create the product list

Create an array called products with these exact product IDs: 3, 1, 4, 4, 5, 3, 3, 1, 6, 4

DSA Typescript

// Your code here

Hint

Use const products = [3, 1, 4, 4, 5, 3, 3, 1, 6, 4]; to create the array.

2

Set the number of top products to find

Create a variable called k and set it to 3 to find the top 3 frequent products.

DSA Typescript

const products = [3, 1, 4, 4, 5, 3, 3, 1, 6, 4];
// Your code here

Hint

Use const k = 3; to set the number of top products.

3

Count frequencies and find top k using a min-heap

Create a Map called freqMap to count frequencies of each product in products. Then create a min-heap using an array called minHeap to keep top k frequent products. Use a helper function heapify to maintain the heap property. Insert products into minHeap based on frequency and remove the smallest frequency when size exceeds k.

DSA Typescript

const products = [3, 1, 4, 4, 5, 3, 3, 1, 6, 4];
const k = 3;
// Your code here

Hint

Use a Map to count frequencies. Use an array as a min-heap and a heapify function to keep smallest frequency on top. Push each product-frequency pair and remove smallest when heap size exceeds k.

4

Print the top k frequent products

Create an array called topK that extracts product IDs from minHeap. Then print topK.

DSA Typescript

const products = [3, 1, 4, 4, 5, 3, 3, 1, 6, 4];
const k = 3;

const freqMap = new Map();
for (const product of products) {
    freqMap.set(product, (freqMap.get(product) ?? 0) + 1);
}

function heapify(arr: [number, number][], i: number, size: number) {
    let smallest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left = 0) {
        heapify(minHeap, i, currentSize);
        i--;
    }
    if (currentSize > k) {
        minHeap[0] = minHeap[currentSize - 1];
        minHeap.pop();
        heapify(minHeap, 0, currentSize - 1);
    }
}

// Extract product IDs from minHeap and print
// Your code here

Hint

Use minHeap.map(item => item[0]) to get product IDs. Then print the array.