Top K Frequent Elements Using Heap in DSA Typescript - Deep Dive

Overview - Top K Frequent Elements Using Heap

What is it?

Top K Frequent Elements Using Heap is a method to find the most common items in a list. It uses a special data structure called a heap to keep track of the top items efficiently. Instead of sorting the entire list, it focuses only on the most frequent elements. This helps when the list is very large and we only want a few top results.

Why it matters

Without this method, finding the most frequent items would require sorting the whole list, which can be slow and use a lot of memory. Using a heap makes the process faster and more efficient, especially for big data. This is important in real life for things like showing popular search terms, trending topics, or common errors quickly.

Where it fits

Before learning this, you should understand arrays, hash maps (dictionaries), and basic sorting. After this, you can learn about more advanced heap operations, priority queues, and other selection algorithms like Quickselect.

Mental Model

Core Idea

Use a heap to keep track of the top K frequent elements by frequency, so you only store the most important items without sorting everything.

Think of it like...

Imagine you are at a party and want to remember the top 3 most popular songs played. Instead of remembering every song, you keep a small list that updates only when a new song is more popular than the least popular in your list.

Input array: [1,1,1,2,2,3]
Frequency map:
  1 -> 3
  2 -> 2
  3 -> 1

Min-heap (size K=2) stores frequencies:
  Step 1: push (1,3) -> heap: [(1,3)]
  Step 2: push (2,2) -> heap: [(1,3), (2,2)]
  Step 3: push (3,1) -> heap size > 2, pop smallest freq (3,1) removed

Result heap contains top 2 frequent elements: 1 and 2

Build-Up - 7 Steps

1

Foundation

Counting Frequencies with a Map

Concept: Learn how to count how many times each element appears using a map.

Given an array of numbers, create a map where keys are numbers and values are counts. For example, for [1,1,2], the map is {1:2, 2:1}. This helps us know which elements are frequent.

Result

{"1":2,"2":1}

Understanding frequency counting is the base for finding the most common elements.

2

Foundation

Understanding Heaps and Their Role

Concept: Introduce heaps as a way to keep track of smallest or largest elements efficiently.

A heap is a special tree-based structure where the smallest (min-heap) or largest (max-heap) element is always at the top. This lets us quickly add or remove elements while keeping order. For top K frequent elements, a min-heap of size K keeps the K largest frequencies.

Result

Min-heap example with elements [3,1,2]: top is 1 (smallest).

Knowing heaps lets us manage the top K elements without sorting all data.

3

Intermediate

Building Frequency Map and Heap Together

🤔Before reading on: do you think we should use a min-heap or max-heap to keep top K frequent elements? Commit to your answer.

Concept: Combine frequency counting with a min-heap to track the top K frequent elements efficiently.

First, count frequencies using a map. Then, create a min-heap that stores pairs of (element, frequency). For each element in the map, push it into the heap. If the heap size exceeds K, remove the smallest frequency element. This way, the heap always contains the top K frequent elements.

Result

For input [1,1,1,2,2,3] and K=2, heap ends with elements 1 and 2.

Using a min-heap of size K ensures we only keep the most frequent elements, saving time and space.

4

Intermediate

Implementing Min-Heap in TypeScript

🤔Before reading on: do you think TypeScript has a built-in heap? How would you implement one if not?

Concept: Learn how to implement a simple min-heap in TypeScript to support push and pop operations.

TypeScript does not have a built-in heap, so we create a class with an array to store elements. We add methods to insert (push) and remove (pop) the smallest element, maintaining the heap property by swapping elements up or down as needed.

Result

Min-heap class with push and pop methods that keep smallest element on top.

Implementing a heap yourself deepens understanding of how priority queues work under the hood.

5

Intermediate

Extracting Top K Elements from Heap

Concept: After building the heap, learn how to get the top K frequent elements from it.

Once the heap contains K elements, repeatedly pop from the heap to get elements from smallest to largest frequency. Reverse the result if needed to get descending order. This gives the top K frequent elements.

Result

For heap with elements (1,3), (2,2), popping yields [2,1], reversed to [1,2].

Extracting elements from the heap gives the final answer in correct order.

6

Advanced

Optimizing with Custom Comparator in Heap

🤔Before reading on: do you think the heap should compare elements by value or frequency? Commit to your answer.

Concept: Use a custom comparator function in the heap to compare elements by frequency instead of value.

Modify the heap to accept a comparator that compares frequencies of elements. This ensures the heap orders elements by frequency, not by their actual value. This is crucial for the top K frequent elements problem.

Result

Heap orders elements by frequency, smallest frequency on top.

Custom comparators let heaps solve a wider range of problems beyond simple numeric order.

7

Expert

Handling Large Data and Streaming Inputs

🤔Before reading on: do you think this heap approach works well if data is too big to fit in memory? Commit to your answer.

Concept: Explore how to adapt the heap method for very large or streaming data where you cannot store all frequencies at once.

For huge data, use approximate counting or streaming algorithms like Count-Min Sketch to estimate frequencies. Then use a heap on these estimates to find top K elements. This trades some accuracy for memory efficiency and speed.

Result

Approximate top K frequent elements with limited memory and fast updates.

Knowing limits of exact methods and how to adapt them is key for real-world big data problems.

Under the Hood

The algorithm first counts frequencies using a hash map, which stores each element's count. Then it uses a min-heap of fixed size K to keep track of the top K elements by frequency. When a new element's frequency is higher than the smallest in the heap, the smallest is removed and the new element is added. This keeps the heap size constant and operations efficient. The heap maintains order by swapping elements up or down to keep the smallest frequency at the root.

Why designed this way?

Sorting all elements by frequency would take O(n log n) time, which is slow for large n. Using a heap reduces this to O(n log k), where k is usually much smaller than n. This design balances speed and memory use. Alternatives like full sorting or using balanced trees were less efficient or more complex.

Frequency Map:
┌─────────────┐
│ Element:Freq│
│ 1 : 3      │
│ 2 : 2      │
│ 3 : 1      │
└─────────────┘

Min-Heap (size K=2):
┌─────────────┐
│ (2,2)      │  <- root (smallest freq)
│ (1,3)      │
└─────────────┘

Insert (3,1):
Heap size > K, remove root (3,1) discarded

Final heap:
┌─────────────┐
│ (2,2)      │
│ (1,3)      │
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think sorting the entire array is the fastest way to find top K frequent elements? Commit yes or no.

Common Belief: Sorting the entire array or frequency list is the best way to find top K frequent elements.

Reality: Sorting all elements takes more time than using a heap, especially when K is much smaller than the number of unique elements.

Why it matters: Using full sorting wastes time and resources, making the program slower and less scalable.

Quick: Do you think a max-heap is better than a min-heap for this problem? Commit your answer.

Common Belief: A max-heap should be used to keep the top K frequent elements.

Reality: A min-heap of size K is better because it keeps the smallest frequency at the top, allowing easy removal when a more frequent element appears.

Why it matters: Using a max-heap would require storing all elements or more complex logic, increasing memory and time costs.

Quick: Do you think the heap stores the elements themselves or just frequencies? Commit your answer.

Common Belief: The heap only needs to store frequencies to find top K elements.

Reality: The heap must store both elements and their frequencies to know which elements are the most frequent.

Why it matters: Storing only frequencies loses the link to which element they belong, making the result meaningless.

Quick: Do you think this method works well for streaming data without modifications? Commit yes or no.

Common Belief: The heap method works directly on streaming data to find top K frequent elements.

Reality: For streaming data, the method needs adaptations like approximate counting because you cannot store all frequencies at once.

Why it matters: Using the exact heap method on streaming data can cause memory overflow or slow performance.

Expert Zone

1

The choice of min-heap vs max-heap depends on whether you want to keep the smallest or largest frequencies at the root for efficient replacement.

2

Heap operations have O(log k) complexity, so keeping k small is crucial for performance in large datasets.

3

Custom comparators in heaps allow flexible ordering, enabling solutions for various frequency-based problems beyond just numbers.

When NOT to use

Avoid this heap approach when K is close to the number of unique elements, as sorting might be simpler. For streaming or very large data, use approximate algorithms like Count-Min Sketch or Space-Saving algorithms instead.

Production Patterns

In real systems, this method is used for trending topics, autocomplete suggestions, and error log analysis. Often combined with caching and approximate counting to handle scale and speed requirements.

Connections

Priority Queue

Heap is the underlying data structure for priority queues.

Understanding heaps helps grasp how priority queues efficiently manage elements by priority, which is essential in scheduling and pathfinding.

Streaming Algorithms

Top K frequent elements using heap is a foundation for streaming frequency estimation.

Knowing the heap method clarifies why streaming algorithms need approximations and how they build on exact frequency counting.

Economics - Market Basket Analysis

Finding frequent elements is similar to identifying popular product combinations in sales data.

Recognizing frequent patterns in data helps businesses optimize inventory and marketing, showing how algorithms impact real-world economics.

Common Pitfalls

#1 Using a max-heap of all elements instead of a min-heap of size K.

Wrong approach:

const heap = new MaxHeap();
for (const [num, freq] of freqMap) {
heap.push([num, freq]);
}
const result = [];
for (let i = 0; i < k; i++) {
result.push(heap.pop()[0]);
}

Correct approach:

const heap = new MinHeap();
for (const [num, freq] of freqMap) {
heap.push([num, freq]);
if (heap.size() > k) heap.pop();
}
const result = [];
while (heap.size() > 0) {
result.push(heap.pop()[0]);
}
result.reverse();

Root cause:

Confusing which heap type keeps the smallest frequency on top for efficient replacement.

#2 Storing only frequencies in the heap without elements.

Wrong approach:

for (const freq of freqMap.values()) {
heap.push(freq);
if (heap.size() > k) heap.pop();
}

Correct approach:

for (const [num, freq] of freqMap) {
heap.push([num, freq]);
if (heap.size() > k) heap.pop();
}

Root cause:

Not associating frequencies with their elements loses the identity of top elements.

#3 Not using a custom comparator to compare frequencies in the heap.

Wrong approach:

class MinHeap {
// compares elements directly, not frequencies
compare(a, b) { return a - b; }
}

Correct approach:

class MinHeap {
// compares frequencies stored in pairs
compare(a, b) { return a[1] - b[1]; }
}

Root cause:

Default comparison does not order elements by frequency, breaking the algorithm.

Key Takeaways

Counting element frequencies is the first step to find the most common items.

A min-heap of fixed size K efficiently keeps track of the top K frequent elements by frequency.

Using a custom comparator in the heap ensures elements are ordered by frequency, not value.

This method reduces time complexity from sorting all elements to managing a small heap, improving performance.

For very large or streaming data, approximate methods build on this idea to handle scale.