Mastering Heap Patterns “Top K” : Maintain Heap Of Size K

Here , We understand about Custom Comparator. While practicing Heap problems on LeetCode, I solved three important problems that helped me understand how heaps can solve different problems efficiently:

• LC 692 — Top K Frequent Words
• LC 347 — Top K Frequent Elements
• LC 973 — K Closest Points to Origin

All three use heaps, but each problem teaches a different way to prioritize elements.

Let’s understand them with real-life analogies, C++ code, and the patterns behind them.

1. LC 692 — Top K Frequent Words

Pattern: Hashing + Max Heap + Custom Comparato

Understanding the problem

Given an array of words and an integer k, return the k most frequent words.

If two words have the same frequency, the lexicographically smaller word must come first.

Example:

words = {"i", "love", "leetcode", "i", "love", "coding"};
k = 2;

Output:

{"i", "love"}

Both i and love appear twice. Since i comes before love alphabetically, it ranks first.

Real-life analogy: A popularity ranking system

Imagine a teacher wants to identify the two most popular students based on votes.

• More votes mean a higher rank.
• If two students receive the same votes, their names are ranked alphabetically.

We need a system that follows both rules automatically. That’s exactly what a heap with a custom comparator can do.

Step 1: Count word frequencies

map<string, int> mp;

for (auto word : words) {
    mp[word]++;
}

The map stores each unique word and its frequency.

WordFrequencycoding1i2leetcode1love2

Step 2: Understand the custom comparator

We store each entry as:

{frequency, word}

The comparator must enforce two rules:

1. Higher frequency gets higher priority.
2. If frequencies are equal, the alphabetically smaller word gets higher priority.

struct Compare {
    bool operator()(const pair<int, string>& a,
                    const pair<int, string>& b) {
        if (a.first == b.first) {
            return a.second > b.second;
        }

        return a.first < b.first;
    }
};

How does it work?

Case A: Different frequencies

a = {2, "apple"};
b = {5, "banana"};

return a.first < b.first;  // true

The lower-frequency entry has lower priority, so the word with frequency 5 ranks higher.

Case B: Equal frequencies

a = {3, "mango"};
b = {3, "apple"};

return a.second > b.second;  // true

mango comes after apple alphabetically, so mango gets lower priority.

Remember: in a C++ priority_queue, returning true means the first entry has lower priority than the second. This is why the comparison rules may initially feel opposite to what we expect.

Step 3: Create the heap

priority_queue<
    pair<int, string>,
    vector<pair<int, string>>,
    Compare
> pq;

The three template arguments mean:

• pair<int, string>: what we store.
• vector<pair<int, string>>: the underlying container.
• Compare: the rule that decides priority.

Now insert every frequency-word pair:

for (auto it : mp) {
    pq.push({it.second, it.first});
}

Extract the top k words:

vector<string> ans;

for (int i = 0; i < k; i++) {
    ans.push_back(pq.top().second);
    pq.pop();
}
return ans;

The heap returns i first and love second.

Complexity: With n total words and m unique words, the time complexity is O(n log m + m log m + k log m), and auxiliary space is O(m).

Key takeaway

LC 692 taught me that a heap is not just about finding the largest or smallest element. A custom comparator lets us define exactly what “highest priority” means.

2. LC 347 — Top K Frequent Elements

Pattern: Hashing + Max Heap

Understanding the problem

Given an integer array, return the k most frequent elements.

Get Harsh Jaiswal’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Example:

nums = {1, 1, 1, 2, 2, 3};
k = 2;

Output:

{1, 2}

Real-life analogy: A product sales leaderboard

Imagine an online store wants to find its two best-selling products.

• Product 1 sold 3 units.
• Product 2 sold 2 units.
• Product 3 sold 1 unit.

Instead of manually sorting every product, we can count sales and use a max heap to retrieve the highest-frequency products first.

How it works

Step 1: Count each number’s frequency.

Step 2: Insert {frequency, element} into the max heap.

Step 3: Pop the heap k times and collect each element.

Because the default priority_queue<pair<int,int>> compares the first value first, the highest frequency appears at the top. If frequencies tie, the larger integer appears first, which is acceptable because LC 347 does not require a particular output order.

Complexity: With m unique numbers, the time complexity is O(n log m + m log m + k log m), with O(m) auxiliary space.

Key takeaway

LC 347 helped me understand the classic frequency counting + max heap pattern.

3. LC 973 — K Closest Points to Origin

Pattern: Distance Calculation + Min Heap

Understanding the problem

Given points on a 2D plane, return the k points closest to the origin (0,0).

Example:

points = {{1,3}, {-2,2}, {5,8}, {0,1}};
k = 2;

Output can be:

{{0,1}, {-2,2}}

Real-life analogy: Finding the nearest delivery locations

Imagine a delivery service operating from a warehouse at (0,0).

There are many delivery locations, and the service needs to identify the two closest ones.

We calculate each location’s distance from the warehouse and use a min heap to retrieve the closest locations first.

Step 1: Calculate squared distance

The Euclidean distance is:

[
d=\sqrt{x²+y²}
]

For comparison, we can use squared distance instead:

[
d²=x²+y²
]

The square root is unnecessary because squaring preserves the order of nonnegative distances.

How it works

Step 1: Calculate the squared distance of every point.

Step 2: Store {distance, index} in a min heap.

Step 3: Extract the smallest k distances and use their indices to retrieve the original points.

The greater<pair<int,int>> comparator creates a min heap. The smallest distance appears at the top.

Complexity: For n points, inserting all points and extracting k takes O(n log n + k log n) time and O(n) auxiliary space.

Key takeaway

LC 973 taught me that heaps can prioritize elements based on a calculated property, not just their original values.

4. What these three problems taught me

ProblemCore patternPriority rule

LC 692Frequency + Custom HeapHighest frequency; alphabetical tie-break

LC 347Frequency + Max HeapHighest frequency

LC 973Distance + Min HeapSmallest distance

5. Final revision notes

• Max heap: By default, the largest value comes first.
• Min heap: Use greater<T> to prioritize the smallest value.
• Frequency problems: Count occurrences first, then prioritize by frequency.
• Custom comparator: Useful when the problem has multiple ranking rules.
• Distance problems: Calculate the relevant distance or score, then use a heap to retrieve the best candidates.
• Optimization: When k is much smaller than the number of unique elements, a heap limited to size k can reduce the heap-related work to O(m log k) after frequency counting.

Solving these three problems helped me understand that the most important part of a heap problem is not just choosing a min heap or max heap — it’s deciding what priority each element should have.

👋 Connect with Me:
🔎LEETCODE :- https://leetcode.com/u/HARSHJAISWAL2707/

👤LinkedIn :- https://www.linkedin.com/in/mr-harsh-jaiswal-76691a32a/

Written by Mr. Harsh Jaiswal — B.Tech CSE | DSA & Web Development

#TopK #Heap #Leetcode #DSA #CodingInterview #EnjoyProblems